Два указателя и скользящее окно

Два бегунка вместо двух вложенных циклов: превращаем O(n²) в O(n) на задачах про подотрезки и пары.

Два указателя — приём, при котором по массиву движутся два индекса, и за счёт монотонности их перемещения вся работа укладывается в один линейный проход.

Зачем это нужно

Очень многие задачи естественно решаются двойным циклом за O(n^2): перебрать все пары, все подотрезки, все подстроки. Но при n = 10^5 квадрат не проходит. Метод двух указателей часто снижает сложность до O(n), используя простое наблюдение: когда мы сдвигаем один указатель, второму не нужно возвращаться назад — он тоже движется только вперёд. Это превращает вложенный перебор в один согласованный проход.

Схема 1. Два указателя с разных концов

Классика: в отсортированном массиве найти пару с заданной суммой. Наивно — все пары за O(n^2). Умно — поставить указатели на концы и двигать их навстречу.

a = [1, 2, 4, 7, 11, 15]
target = 15
i, j = 0, len(a) - 1
res = None
while i < j:
    s = a[i] + a[j]
    if s == target:
        res = (a[i], a[j]); break
    elif s < target:
        i += 1            # сумма мала — увеличиваем левый
    else:
        j -= 1            # сумма велика — уменьшаем правый
print("Пара:", res)

Почему это работает? Если a[i]+a[j] слишком мало, увеличить сумму можно только сдвинув левый указатель вправо (правый и так максимален). Симметрично для «слишком много». Поэтому каждый указатель проходит массив максимум один раз — итого O(n).

Вывод:

Пара: (4, 11)

Схема 2. Скользящее окно

Скользящее окно — частный, но крайне важный случай: оба указателя движутся в одну сторону, образуя «окно» [left, right], которое мы расширяем справа и сжимаем слева. Решим задачу: самый длинный подотрезок с суммой не больше S (все числа положительные).

a = [2, 1, 5, 1, 3, 2]
S = 8
left = 0
cur = 0        # сумма внутри окна [left, right]
best = 0
for right in range(len(a)):
    cur += a[right]            # расширили окно вправо
    while cur > S:            # окно стало «тяжёлым» — сжимаем слева
        cur -= a[left]
        left += 1
    best = max(best, right - left + 1)
print("Макс длина подотрезка с суммой <=", S, ":", best)

Идея: указатель right добавляет элементы, а left «догоняет» только когда сумма превысила лимит. Поскольку left никогда не идёт назад, суммарно оба индекса делают O(n) шагов — несмотря на вложенный while. Это и есть фокус амортизации: внутренний цикл в сумме по всем итерациям выполнится не более n раз.

Вывод:

Макс длина подотрезка с суммой <= 8 : 3

Окно с подсчётом: подстрока без повторов

Скользящее окно отлично работает со строками. Найдём длину самой длинной подстроки без повторяющихся символов — типичная задача на собеседованиях и олимпиадах.

s = "abcabcbb"
last = {}          # символ -> последний индекс, где видели
left = 0
best = 0
for right, ch in enumerate(s):
    if ch in last and last[ch] >= left:
        left = last[ch] + 1     # сдвигаем левую границу за повтор
    last[ch] = right
    best = max(best, right - left + 1)
print("Длина самой длинной подстроки без повторов:", best)

Окно [left, right] всегда содержит только уникальные символы. Когда встречаем повтор внутри окна, перепрыгиваем left за прошлое вхождение. Один проход — O(n).

Вывод:

Длина самой длинной подстроки без повторов: 3

Когда применять

• Два указателя с концов: массив отсортирован, ищем пару/тройку с условием на сумму.
• Скользящее окно: ищем подотрезок/подстроку, удовлетворяющий монотонному условию («сумма ≤ S», «не больше k различных», «без повторов»).
• Признак применимости окна: при расширении вправо условие «портится» в одну сторону, и его можно «починить» сдвигом слева.

Подводные камни

• Окно работает не всегда. Для «суммы ≤ S» с отрицательными числами окно ломается (сжатие слева не обязательно уменьшает сумму) — там нужны префиксные суммы и другие приёмы.
• Считай длину правильно: длина окна [left, right] — это right - left + 1, частая ошибка off-by-one.
• Не забывай обновлять ответ после восстановления корректности окна, а не до.

Итог

• Два указателя превращают O(n^2) перебор пар/подотрезков в O(n) за счёт того, что индексы не ходят назад.
• Указатели с концов — для пар в отсортированном массиве; скользящее окно — для подотрезков с монотонным условием.
• Внутренний while в окне не делает алгоритм квадратным: суммарно он выполняется O(n) раз (амортизация).
• Следи за знаком чисел и за формулой длины окна.