Как гарантировать проверку всех элементов массива при поиске пары чисел?

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

Умеете ли вы доказать, что алгоритм не пропускает пары, а не просто написать код, прошедший на одном примере. Интервьюер смотрит на инвариант цикла, граничные случаи и на то, не складывается ли элемент сам с собой. Следом обычно просят найти все пары, а не первую.

Как отвечать

Покажите три подхода и для каждого объясните, почему ничего не теряется:

• перебор: for i in range(n) и вложенный for j in range(i + 1, n). Старт с i + 1 гарантирует, что каждая неупорядоченная пара проверяется ровно один раз и элемент не складывается сам с собой. Время O(n²), память O(1);
• множество за один проход: для каждого x сначала проверяете target - x in seen, потом делаете seen.add(x). В seen лежат все элементы левее текущего, поэтому, когда вы дойдёте до второго элемента пары, первый уже будет там. Время O(n), память O(n);
• два указателя на отсортированном массиве: while left < right; сумма меньше цели, сдвигаете left, больше, сдвигаете right. Инвариант: отброшенный элемент не даёт цель ни с одним из оставшихся, ведь при сумме меньше цели a[left] с любым элементом не правее right даст ещё меньше. Время O(n log n) из-за сортировки.

Если нужны все пары, не выходите из цикла по первой находке: копите результат, а повторяющиеся значения считайте через collections.Counter. И назовите тесты: пустой массив, один элемент, отрицательные числа, [4, 4] при цели 8, пара на самых краях, пары нет вовсе.

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

Кладут элемент в seen до проверки. Тогда [4] при цели 8 вернёт пару (4, 4), которой в массиве нет.

Ошибаются на единицу: range(i + 1, n - 1) во внутреннем цикле или while left <= right. Первое теряет последний элемент, второе складывает элемент сам с собой.

Сортируют массив, когда нужно вернуть индексы. После sort() исходные позиции потеряны, поэтому сортируют пары (значение, индекс) или вместо множества берут словарь {значение: индекс}.