Доказательство корректности метода двух указателей

Метод двух указателей - популярный алгоритмический приём для поиска пары элементов с заданной суммой в двух отсортированных массивах. Классическая задача: даны отсортированные по возрастанию массивы A (длины N) и B (длины M), а также массив целей C. Для каждого элемента c из C нужно определить, существуют ли i, j такие, что A[i] + B[j] == c. Алгоритм использует два указателя: один (i) начинает с начала A, второй (j) - с конца B. На каждом шаге сумма A[i] + B[j] сравнивается с c: если сумма больше, j сдвигается влево; если меньше - i сдвигается вправо. Процесс продолжается, пока указатели не встретятся или не будет найдена искомая пара.

Почему метод двух указателей работает?

Корректность алгоритма основана на монотонности отсортированных массивов. Рассмотрим инвариант: на каждом шаге все возможные пары (i, j), которые могли бы дать сумму c, находятся в прямоугольнике между текущими i и j. Если A[i] + B[j] > c, то для любого j' ≥ j сумма A[i] + B[j'] ≥ A[i] + B[j] > c (так как B отсортирован по возрастанию). Значит, ни одна пара с текущим i и любым j' ≥ j не даст c. Следовательно, j можно смело уменьшать. Аналогично, если A[i] + B[j] < c, то для любого i' ≤ i сумма A[i'] + B[j] ≤ A[i] + B[j] < c (так как A отсортирован), поэтому i можно увеличивать. Таким образом, алгоритм не пропускает ни одной потенциально подходящей пары.

Гарантия, что указатели не перескочат через решение

Вопрос о «перескоке» связан с тем, что при сдвиге указателей мы можем случайно пропустить пару, которая даёт нужную сумму. Доказательство: предположим, существует пара (i*, j*), для которой A[i*] + B[j*] == c. В начальный момент i = 0, j = M-1. Пока i < i* и j > j*, алгоритм будет двигать указатели, но не пересечёт границу i* или j*. Как только i достигнет i* или j достигнет j*, дальнейшие шаги приведут к проверке этой пары. Например, если сначала i дошёл до i*, а j всё ещё больше j*, то A[i*] + B[j] > c (так как B[j] > B[j*]), и j будет уменьшаться, пока не станет равным j*. Аналогично, если j дошёл до j*, а i меньше i*, то A[i] + B[j*] < c, и i будет расти до i*. Таким образом, алгоритм обязательно проверит искомую пару, если она существует. Указатели никогда не «перескочат» через решение, потому что движение всегда происходит в сторону уменьшения разницы с целевой суммой.

Анализ сложности алгоритма

Временная сложность: сортировка массивов A и B занимает O(N log N + M log M). Сам поиск для каждого элемента C выполняется за O(N + M), так как в худшем случае указатели проходят все элементы. Итоговая сложность: O(N log N + M log M + K * (N + M)). Пространственная сложность: O(1) без учёта входных данных.

Типичные ошибки при реализации

• Забыть отсортировать массивы - алгоритм корректен только для отсортированных данных.
• Неправильно обрабатывать случай, когда один из массивов пуст: нужно сразу выводить 'NO' для всех целей.
• Игнорировать граничные условия: если N=0 или M=0, цикл while не выполнится, и результат будет 'NO'.
• Путать направление движения указателей: при сумме больше цели уменьшаем j, при сумме меньше - увеличиваем i.

Пример работы алгоритма

Пусть A = [1, 3, 5], B = [2, 4, 6], C = [7, 10]. Для c = 7: i=0, j=2 → сумма 1+6=7 → YES. Для c = 10: i=0, j=2 → 1+6=7 < 10 → i=1; 3+6=9 < 10 → i=2; 5+6=11 > 10 → j=1; 5+4=9 < 10 → i=3 (выход) → NO. Результат: YES, NO.