Два указателя

Два указателя — приём, когда по массиву одновременно двигаются два индекса. Он превращает многие решения «перебрать все пары» из n² шагов в n шагов.

Указатели навстречу

Задача: в отсортированном списке найти два числа с суммой x. Перебор всех пар — n² проверок. Но можно умнее:

a = [1, 3, 4, 6, 8, 11]
x = 10
i, j = 0, len(a) - 1
while i < j:
    s = a[i] + a[j]
    if s == x:
        print(a[i], a[j])   # 4 6
        break
    elif s < x:
        i += 1    # сумма мала — берём левое число побольше
    else:
        j -= 1    # сумма велика — берём правое число поменьше

Почему это верно: если a[i] + a[j] меньше x, то a[i] не подходит ни с каким элементом левее j (все они ещё меньше) — его можно выбросить. Аналогично для правого конца. Каждый шаг отбрасывает один элемент, поэтому шагов не больше n.

Указатели в одном направлении: слияние

Два указателя могут идти по двум разным спискам. Например, чтобы найти общие элементы двух отсортированных списков:

a = [1, 2, 4, 5, 7]
b = [2, 3, 5, 7, 9]
i = j = 0
common = []
while i < len(a) and j < len(b):
    if a[i] == b[j]:
        common.append(a[i]); i += 1; j += 1
    elif a[i] < b[j]:
        i += 1
    else:
        j += 1
print(common)    # [2, 5, 7]

Всегда двигаем указатель, который смотрит на меньшее число: оно уже не может совпасть ни с чем дальше в другом списке.

Точка с запятой ; позволяет записать несколько команд в одной строке — так можно, но злоупотреблять не стоит.

Окно переменной длины

Самое частое применение — скользящее окно: отрезок [left, right], правая граница идёт вперёд по одному элементу, а левая догоняет, когда окно стало «плохим».

Пример: длина самого длинного отрезка, где все числа чётные:

a = [2, 4, 1, 6, 8, 10, 3, 2]
left = 0
best = 0
for right in range(len(a)):
    if a[right] % 2 == 1:     # окно с нечётным числом плохое —
        left = right + 1      # начинаем новое окно после него
    best = max(best, right - left + 1)
print(best)    # 3  (6, 8, 10)

Общая схема окна:

left = 0
for right in range(n):
    # 1. добавить a[right] в окно
    # 2. пока окно плохое — убрать a[left] и сдвинуть left
    # 3. окно [left, right] хорошее — обновить ответ

Чтобы схема работала, нужно свойство: если окно хорошее, то и любое окно внутри него хорошее. Тогда левой границе никогда не нужно возвращаться назад.

Поддерживать «что лежит в окне» помогают переменные (сумма, счётчик) или словарь (сколько раз каждый элемент встречается в окне).

Сколько это стоит

Хотя внутри for может быть while, указатель left за всю программу сдвинется не больше n раз. Поэтому суммарно шагов около 2n, а не n².

Итог

• указатели навстречу — поиск пары в отсортированном массиве;
• указатели по двум спискам — слияние, пересечение;
• скользящее окно: right идёт вперёд, left догоняет, когда окно стало плохим;
• каждый указатель проходит массив один раз — получается порядка n шагов.