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

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

Понимаете ли вы, чем платите за линейное время в задаче two sum: интервьюер хочет услышать O(n) дополнительной памяти и объяснение, откуда она берётся. Следом почти всегда спрашивают, можно ли обойтись без словаря и что тогда станет со временем.

Как отвечать

Сначала сам алгоритм: идём по списку, для каждого x проверяем, есть ли в словаре target - x, и только если нет, кладём x с его индексом. Один проход, проверка in в среднем O(1).

Дальше про память:

• асимптотика: в худшем случае пары нет или она в самом конце, и в словарь попадают почти все n элементов. Это O(n) дополнительной памяти. В лучшем случае ответ находится сразу, и память O(1);
• константа: словарь в CPython это хеш-таблица, которая расширяется, когда заполнена примерно на две трети, поэтому ячеек всегда больше, чем ключей. Плюс сами объекты int, если они не из кэша маленьких чисел. На миллионе элементов это десятки мегабайт, проверить можно через sys.getsizeof или tracemalloc;
• что хранить: если нужен только факт существования пары, хватит set, он легче словаря, потому что не хранит значений;
• альтернатива: отсортировать и идти двумя указателями с краёв. Время O(n log n), зато нет хеш-таблицы. Но list.sort() меняет исходный список и теряет индексы, а sorted() создаёт копию, то есть снова O(n).

Итог формулируйте как компромисс: словарь даёт O(n) по времени ценой O(n) памяти, сортировка экономит память ценой времени и исходного порядка.

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

Говорят «словарь O(1) по памяти», путая стоимость одной операции с объёмом всей структуры.

Сначала заполняют словарь целиком, а пару ищут вторым проходом. Асимптотика та же, но теряется ранний выход, а при повторяющихся числах легко вернуть один и тот же индекс дважды.

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