Два указателя
Метод двух указателей широко используется при решении различных задач, в которых асимптотика не должна превышать O(n).
Рассмотрим идею метода двух указателей на примере следующей задачи.
Задача
В массиве неотрицательных чисел необходимо найти любой непрерывный отрезок с суммой элементов, равной k.
В методе двух указателей, указателями называются индексы начала и конца рассматриваемого отрезка (а не в смысле того, что они имеют тип
pointer).
Решить задачу методом двух указателей можно, если на каждом шаге алгоритма мы можем перемещать один из указателей вправо. Другими словами, при увеличении значения одного указателя значение другого указателя может только увеличиваться. Таким образом, мы не перебираем все значения отрезка заново, а может просто продолжать вычисления с предыдущего значения.
Так как мы двигаем два указателя от начала массива к концу, то каждый из них будет принимать не более
n значений. Следовательно, количество действий алгоритмы не превысит
2n и ассимптотика алгоритма останется
O(n).
Идея решения данной задачи будет заключаться в следующем.
1) Зафиксируем первый (
i) и второй (
j) указатель на первом элементе массива.
2) Начальное значение суммы положим равным первому элементу массива (на который указывают оба указателя).
3) Далее, будем двигать правый указатель (
j) и добавлять к сумме значения элементов
a[j]. После добавления очередного элемента у нас сумма может стать либо больше, либо равной искомой (если она меньше искомой, то мы будем дальше добавлять значения элементов к сумме).
- Если на текущем шаге сумма элементов станет равной искомому значению, значит мы получили наш ответ (нужные значения
i и
j.
- Если сумма элементов на текущем шаге стала больше искомого значения, значит необходимо из суммы убрать один элемент. Какой? Очевидно, что тот, на который указывает левый указатель
i. Тогда уберем из суммы данный элемент
a[i] и увеличим значение
i. 4) Так будем действовать до тех пор, пока либо не найдем искомую сумму, либо правый указатель не дойдет до конца массива. Один из вариантов реализации данной идеи представлен в программе ниже (язык Python).
n = 5
target = 7
nums = [1, 2, 3, 4, 5]
i = 0
j = 0
s = nums[j]
while j < n:
if s == target:
break
if s < target:
j += 1
if j < n:
s += nums[j]
else:
s -= nums[i]
i += 1
if s == target:
print(i, j)
else:
print(-1, -1)