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

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

Видите ли вы переход от перебора пар за O(n²) к одному проходу за O(n) и понимаете ли, чем за это платите. Следом почти всегда меняют условие: вернуть индексы, найти все пары, или массив уже отсортирован.

Как отвечать

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

def two_sum(nums, target):
    seen = {}
    for i, x in enumerate(nums):
        j = seen.get(target - x)
        if j is not None:
            return j, i
        seen[x] = i
    return None

• порядок операций: сначала проверка, потом запись. Так число не складывается само с собой, а пара из двух троек при target = 6 находится корректно;
• dict или set: если нужны индексы, храните в словаре значение и индекс, если только сами числа, хватит set;
• сложность: O(n) по времени в среднем и O(n) по памяти. Поиск в dict в среднем O(1), но при массовых коллизиях деградирует до O(n);
• отсортированный массив: два указателя с концов дают O(n) без дополнительной памяти. Для несортированного это уже O(n log n) из-за сортировки, и исходные индексы теряются.

Для варианта «все уникальные пары» результат складывают в set кортежей (min(a, b), max(a, b)), а для подсчёта числа пар с повторами удобен collections.Counter.

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

Сначала кладут весь массив в словарь, а потом ищут дополнение. При target = 10 и единственной пятёрке в массиве функция находит пару из одного элемента.

Пишут if target - x in nums. Это поиск по списку, он линейный, и итоговая сложность остаётся квадратичной, хотя код выглядит коротким.

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