Как устроено решение задачи поиска пары чисел с заданной суммой
Что проверяют
Умеете ли вы уйти от перебора к линейному решению и честно назвать цену: время против памяти. Следом обычно меняют условие: вернуть индексы, найти все пары, массив уже отсортирован или не помещается в память.
Как отвечать
Сначала задайте уточняющие вопросы: нужны значения или индексы, одна пара или все, есть ли повторы и отрицательные числа, можно ли менять входной список. Потом три подхода по возрастанию качества:
- перебор: два вложенных цикла по парам, O(n²) по времени, O(1) по памяти. Годится как отправная точка;
- хэш-таблица за один проход: идём по
enumerate(nums), для каждого числа считаем дополнение до целевой суммы и ищем его в словареseen, где ключ это число, а значение его индекс. Поиск вdictиsetв среднем O(1), итог O(n) по времени и O(n) по памяти. Проверять надо до добавления текущего числа, иначе при сумме 10 и единственной пятёрке найдётся несуществующая пара; - сортировка и два указателя: O(n log n) из-за сортировки и O(1) дополнительной памяти, если сортировать на месте. Указатели идут с краёв: сумма меньше цели двигает левый, больше двигает правый. Если массив уже отсортирован, остаётся O(n) без лишней памяти.
Для всех уникальных пар удобно собирать результат в set кортежей вида (min(a, b), max(a, b)), а при повторах считать частоты через collections.Counter.
Покажите, что понимаете оговорку: O(1) у словаря это средняя оценка, при массовых коллизиях поиск деградирует. Этого обычно не требуют, но упоминание засчитывают.
Где спотыкаются
Пишут «оптимальный» вариант с if complement in nums[i+1:]. Проверка вхождения в список линейная, срез ещё и копирует его, итог снова O(n²).
Вызывают nums.sort() на входном списке и молча портят данные вызывающего кода. Нужен sorted(nums) или хотя бы вопрос интервьюеру. Заодно после сортировки теряются исходные индексы.
Не проверяют крайние случаи: пустой список, один элемент, пара из двух одинаковых чисел, отсутствие ответа. Возвращать при неудаче стоит None, а не строку с сообщением.