Как оптимизировать поиск пары чисел с помощью хэш-таблиц?

Что проверяют

Умеете ли вы превратить квадратичный перебор в один проход и объяснить, откуда берётся выигрыш. На фронтенд-собеседовании заодно смотрят, знаете ли вы Map и Set в JavaScript. Следом просят вернуть индексы, найти все пары или решить без дополнительной памяти.

Как отвечать

Начните с наивного решения: два вложенных цикла, O(n²) по времени. Затем покажите идею: для каждого числа x нужно знать, встречалось ли раньше target - x, а хэш-таблица отвечает на это в среднем за O(1).

function twoSum(nums, target) {
  const seen = new Map();
  for (let i = 0; i < nums.length; i++) {
    const need = target - nums[i];
    if (seen.has(need)) return [seen.get(need), i];
    seen.set(nums[i], i);
  }
  return null;
}

Что проговорить:

• сложность: O(n) по времени в среднем и O(n) по памяти. При массовых коллизиях хэш-таблица деградирует, но на практике это не учитывают;
• порядок операций: сначала проверка, потом запись. Иначе при target = 8 и единственной четвёрке в массиве функция соберёт пару из одного элемента;
• почему Map, а не объект: ключи объекта приводятся к строкам, а у Map есть честный has без путаницы с прототипом и с ложными значениями;
• альтернатива: сортировка и два указателя дают O(n log n) и O(1) дополнительной памяти при сортировке на месте, но исходные индексы теряются;
• варианты задачи: все пары вместо первой, подсчёт пар с повторами (тогда в Map хранят количество), уникальные пары через Set.

Где спотыкаются

Используют объект и проверку if (seen[need]). Если сохранён индекс 0, условие ложно, и пара с первым элементом теряется.

Прячут второй цикл в includes или indexOf внутри for. Код выглядит линейным, а работает за O(n²).

Не уточняют условие: нужны индексы или значения, можно ли брать одно число дважды, бывают ли повторы. Интервьюер часто ждёт именно этих вопросов до начала кода.