Как устроено решение задачи поиска пары чисел с заданной суммой

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

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

Как отвечать

Сначала классика на Python с уточнением условий (индексы или значения, повторы, одна пара или все):

• перебор: O(n²) по времени, отправная точка;
• словарь за один проход: для каждого числа ищем в dict дополнение до цели, O(n) по времени и O(n) по памяти. Проверка идёт до добавления текущего элемента, иначе число, равное половине цели, сложится само с собой;
• сортировка и два указателя: O(n log n), дополнительная память не нужна, если можно сортировать на месте.

Дальше покажите, что знаете векторные варианты и их пределы:

• NumPy через сортировку: np.sort упорядочивает массив, затем np.searchsorted ищет дополнение до цели сразу для всех элементов, и найденные значения сравниваются с искомыми. Это O(n log n) без цикла на Python, отдельно нужно исключить совпадение элемента с самим собой;
• broadcasting: a[:, None] + a[None, :] == target выглядит изящно, но строит матрицу n на n. На 100 тысячах элементов это 10 миллиардов ячеек, памяти не хватит;
• pandas: пары ищутся самосоединением, к таблице добавляется колонка с дополнением, и по ней делается merge с исходной колонкой. Внутри это хэш-соединение, та же идея, что со словарём.

Отдельно про дробные числа. 0.1 + 0.2 == 0.3 в Python даёт False, поэтому точное сравнение с целевой суммой для float ненадёжно. Либо округляйте до нужной точности и храните в словаре целые, либо сортируйте и ищите двумя указателями с допуском, как в np.isclose.

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

Пишут цикл по строкам DataFrame через iterrows() и получают решение, которое на реальном объёме работает минутами.

Решают через broadcasting и не считают память, пока ноутбук не падает с MemoryError.

Сравнивают дробные суммы через == и теряют пары из-за погрешности представления, особенно после масштабирования признаков.