Как найти пару чисел с заданной суммой одним проходом по массиву уникальных чисел?

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

Заметите ли вы, что задача решается за один проход с хеш-таблицей, и проговорите ли сложность и крайние случаи.

Как отвечать

Идея: для каждого числа нужно проверить, встречалось ли раньше дополняющее до суммы. Проверка по множеству стоит константу, поэтому одного прохода достаточно.

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;
}

Проговорите вслух:

• сложность: время линейное, память линейная. Наивное решение двумя циклами квадратично;
• почему проверка идёт до записи: иначе при target = 2 * nums[i] элемент найдёт сам себя. В задаче с уникальными числами это менее важно, но привычка правильная;
• что возвращать: индексы или значения, и что делать, если пары нет. Это стоит уточнить у интервьюера до кода;
• крайние случаи: пустой массив, один элемент, отрицательные числа и ноль (алгоритм с ними работает без изменений).

Полезно назвать альтернативу: если массив отсортирован, ту же задачу решают два указателя с краёв за линейное время и без дополнительной памяти. А если чисел не два, а больше, задача обобщается сортировкой и вложенными указателями.

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

Пишут два вложенных цикла и не предлагают улучшения.

Записывают элемент в множество до проверки и находят пару из одного и того же элемента.

Не уточняют, что возвращать при отсутствии пары, и молча возвращают undefined.