Метод двух указателей очень эффективен при решении большого количества задач. В этой статье мы рассмотрим один пример использования.
Задача
Для заданного отсортированного в возрастающем порядке массива A целых чисел длины n и целого числа X определить, существует ли в нем два различных элемента A[i] и A[j], такие что A[i] + A[j] = X.
Малоэффективное решение
Первое, что приходит в голову, — пройтись по всем парам элементов массива A[i] и A[j] и сравнить их сумму с X. Это можно сделать с помощью вложенного цикла:
Сложность такого алгоритма — O(n²).
Эффективное решение
Теперь применим методов двух указателей. В качестве двух указателей будут выступать две переменные, которые в начале хранят индексы первого и последнего элемента. На каждой итерации будем сравнивать сумму элементов, на которые указывают указатели. Если сумма элементов больше X, то нужно подвинуть правый указатель влево, чтобы сумма элементов уменьшилась (массив отсортирован). Если же сумма элементов меньше нужной, то подвинем левый указатель вправо. И так до тех пор, пока не найдем нужные элементы или же не попадем в ситуацию, когда два указателя определяют один и тот же элемент.
Так как по каждому элементу мы проходимся максимум один раз, то итоговая сложность — O(n).
На простом примере покажем, что выполняет код в процессе работы:
Как это работает?
В данной задаче алгоритм использует тот факт, что массив отсортирован. На каждой итерации, если сумма больше нужной, нам нужно двигать лишь правый указатель влево, так как во всех других случаях сумма только увеличится. Точно такая же логика применяется для случая, когда сумма меньше нужной.
Задача для самостоятельного решения
Для двух заданных отсортированных в возрастающем порядке целочисленных массивов A и B длин n и m соответственно, найти пару самых близких между собой по значению элементов. Более формально: найти такие элементы A[i] и B[j], что их модуль разности минимален по сравнению с другими парами элементов из этих массивов.
Пример. Для заданных массивов {1, 2, 10} и {8, 20, 30} ответом будет пара чисел 10 и 8.