Условие

Дан массив целых чисел nums и целевое число target. Верните индексы двух элементов, которые в сумме дают target. Гарантируется, что ровно одна пара существует. Решение за O(n) времени и O(n) памяти.

Решение

Подход

Идём по массиву один раз. Для каждого nums[i] ищем в хэш-таблице ключ target - nums[i]. Если есть — нашли пару (previous_index, i). Если нет — кладём nums[i] → i в хэш и идём дальше. Это даёт O(n), потому что lookup и insert в хэш-таблицу — амортизированно O(1).

Реализация

def two_sum(nums: list[int], target: int) -> tuple[int, int]:
    seen: dict[int, int] = {}
    for i, x in enumerate(nums):
        need = target - x
        if need in seen:
            return seen[need], i
        seen[x] = i
    raise ValueError("No pair found")

Версии для интервью

«А если решение должно вернуть значения, не индексы» — заменяем return seen[need], i на return need, x.
«А если пары может не быть» — возвращаем None или пустой кортеж вместо exception.
«А если много пар» — собираем в список вместо return и продолжаем цикл, но осторожно с дубликатами по неупорядоченности (i, j) vs (j, i).
«А если массив отсортирован» — два указателя, O(n) без памяти.

Подводные камни

O(n²) решение через два вложенных цикла — типичный ответ-ловушка. Интервьюер ждёт хэш-таблицу.
Записывать в хэш ДО проверки — ошибка. Если target = 2 * nums[i] и в массиве только один такой элемент, вернёте (i, i). Сначала ищем, потом кладём.
target - nums[i] может быть отрицательным; питоновские int не переполняются, но в C++/Java следить.
Дубликаты значений. [3, 3], target = 6 — корректное решение возвращает (0, 1), оба элемента 3 нужны.

Эталонный ответ

Один проход с hash-map: для каждого x смотрим target - x в хэше; если есть — ответ. Иначе кладём x → i и идём дальше. Сначала look-up, потом insert — иначе словите false-pair (i, i). Время O(n), память O(n).

alexeygrigorev/data-science-interviews: Two Sum за O(n)