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

Почти любая задача про массив или строку в первом приближении решается двойным циклом: перебрать все пары индексов или все подотрезки — и посмотреть, что получится. Это честно, это всегда правильно и это O(n²). На n = 1000 такой код отработает мгновенно, на n = 10⁶ он будет считать примерно до конца рабочего дня.

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

Ключевое слово здесь — монотонность. Это не «трюк для собеседований», а конкретное структурное свойство задачи, которое можно сформулировать и доказать. Ниже мы это свойство выпишем строго, научимся проверять его до написания кода и разберём, что происходит, когда оно нарушается (спойлер: код выглядит правильным, проходит примеры и молча врёт).

Предполагается, что вы уже знакомы с языком асимптотики и инвариантов цикла из статьи Анализ алгоритмов — доказательства ниже написаны именно в этих терминах. Многие варианты приёма требуют отсортированного входа, см. Сортировки.

1. Карта приёма: что вообще называют «двумя указателями»

Под одним зонтичным термином прячутся четыре довольно разных алгоритмических схемы. Их объединяет только форма кода — несколько индексов, движущихся по массиву без возвратов, — но интуиция и доказательства у них разные.

Общий знаменатель всех четырёх — амортизационный аргумент: каждый указатель проходит массив не более одного раза, поэтому суммарное число сдвигов ограничено O(n), даже если на отдельной итерации внешнего цикла внутренний указатель сделал сто шагов.

2. Встречные указатели и почему это корректно

2.1 Каноническая задача

Дан отсортированный массив a и число T. Найти два индекса i < j с a[i] + a[j] == T.

Наивно — O(n²) пар. С хеш-таблицей — O(n) времени и O(n) памяти, но сортировка при этом не используется. Два указателя дают O(n) времени и O(1) памяти:

def two_sum_sorted(a: list[int], target: int) -> tuple[int, int] | None:
    """Пара индексов с суммой target в отсортированном массиве. O(n) времени, O(1) памяти."""
    l, r = 0, len(a) - 1
    while l < r:
        s = a[l] + a[r]
        if s == target:
            return l, r
        if s < target:
            l += 1      # сумма слишком мала — увеличиваем меньший элемент
        else:
            r -= 1      # сумма слишком велика — уменьшаем больший
    return None

2.2 Доказательство корректности

Код короткий, но неочевидный: почему, отбрасывая a[l], мы не теряем ответ? Формальный аргумент — через инвариант:

Инвариант. Если искомая пара (i, j) существует, то на каждой итерации выполняется l ≤ i < j ≤ r.

База. Перед первой итерацией l = 0, r = n-1, инвариант тривиален.

Шаг. Пусть инвариант верен и a[l] + a[r] < T. Покажем, что i ≠ l. Допустим i = l. Тогда j ≤ r, а массив отсортирован, значит a[j] ≤ a[r], откуда T = a[i] + a[j] = a[l] + a[j] ≤ a[l] + a[r] < T — противоречие. Значит i > l, и после l += 1 инвариант сохраняется. Случай a[l] + a[r] > T симметричен: тогда j ≠ r.

Завершение. На каждой итерации r - l уменьшается на единицу, поэтому цикл завершается не более чем за n итераций. Если пара существовала, инвариант не давал ей выпасть из [l, r], а единственный способ выйти из цикла с непустым отрезком — это return.

Геометрически это выглядит так: пространство поиска — треугольная матрица всех пар (i, j), и каждый шаг указателя вычёркивает из неё целую строку или целый столбец.

Отсюда сразу видно, где приём работает, а где нет: он требует, чтобы функция f(i, j) = a[i] + a[j] была монотонна по каждому аргументу. Для суммы отсортированного массива это так. Для произведения массива с отрицательными числами — уже нет, и алгоритм сломается.

2.3 Что расширяется до 3sum

Задача «найти тройку с нулевой суммой» решается фиксацией первого элемента и двумя указателями внутри — O(n²) вместо O(n³):

def three_sum(nums: list[int]) -> list[tuple[int, int, int]]:
    """Все уникальные тройки с нулевой суммой. O(n^2) времени, O(1) доп. памяти без учёта ответа."""
    a = sorted(nums)               # O(n log n) — не доминирует
    n, res = len(a), []
    for k in range(n - 2):
        if k > 0 and a[k] == a[k - 1]:
            continue               # пропуск дубликатов на внешнем уровне
        if a[k] > 0:
            break                  # дальше все элементы положительны — нуля не будет
        l, r = k + 1, n - 1
        while l < r:
            s = a[k] + a[l] + a[r]
            if s < 0:
                l += 1
            elif s > 0:
                r -= 1
            else:
                res.append((a[k], a[l], a[r]))
                l += 1
                r -= 1
                while l < r and a[l] == a[l - 1]:
                    l += 1         # пропуск дубликатов внутри
                while l < r and a[r] == a[r + 1]:
                    r -= 1
    return res

Нижняя оценка здесь нетривиальна: 3SUM долгое время считался задачей с «естественной» границей Θ(n²), и на этом предположении построен целый класс условных нижних оценок в вычислительной геометрии (3SUM-hardness). Аллан Грёнлунд и Сет Петти в 2014 году показали слегка субквадратичный алгоритм, но практического значения он не имеет — см. «Threesomes, Degenerates, and Love Triangles».

2.4 Другой класс: «максимум по паре границ»

Задача container with most water: массив высот, выбрать две линии, чтобы прямоугольник между ними имел максимальную площадь — min(h[l], h[r]) · (r - l).

def max_area(h: list[int]) -> int:
    """Максимальная площадь между двумя линиями. O(n) времени, O(1) памяти."""
    l, r, best = 0, len(h) - 1, 0
    while l < r:
        best = max(best, min(h[l], h[r]) * (r - l))
        # двигаем меньшую границу: только у неё есть шанс вырасти
        if h[l] < h[r]:
            l += 1
        else:
            r -= 1
    return best

Аргумент отбрасывания тот же: пусть h[l] < h[r]. Для любого j < r площадь min(h[l], h[j]) · (j - l) ≤ h[l] · (j - l) < h[l] · (r - l), то есть все пары с левой границей l уже проиграли текущему кандидату. Значит, строку l можно вычеркнуть целиком.

Полезная привычка: каждый раз, сдвигая указатель, произнесите вслух, какое множество кандидатов вы этим отбрасываете и почему они все не лучше уже рассмотренного. Если такого предложения не получается — приём неприменим, и код, скорее всего, неверен.

3. Однонаправленные указатели: запись отстаёт от чтения

Вторая схема — «медленный и быстрый», где один указатель читает вход, а второй указывает на позицию записи. Классическое применение — компактификация массива на месте.

def remove_in_place(a: list[int], drop) -> int:
    """Удаляет элементы, для которых drop(x) истинно, сохраняя порядок.
    Возвращает новую длину. O(n) времени, O(1) памяти, стабильно."""
    write = 0
    for read in range(len(a)):        # read — быстрый, write — медленный
        if not drop(a[read]):
            a[write] = a[read]
            write += 1
    return write                       # a[:write] — результат

Инвариант: a[0:write] — это уже отфильтрованный префикс a[0:read] в исходном порядке, а write ≤ read гарантирует, что мы никогда не перезаписываем ещё не прочитанное. Ровно эта схема стоит за std::remove_if в C++, за slices.DeleteFunc в Go и за фазой сжатия (compaction) в mark-compact сборщиках мусора.

Трёхпутевой вариант — голландский флаг Дейкстры, три указателя на одном проходе:

def dutch_flag(a: list[int], pivot: int) -> tuple[int, int]:
    """Переставляет a так, что сначала < pivot, затем == pivot, затем > pivot.
    Возвращает границы средней зоны. O(n) времени, O(1) памяти, один проход."""
    lo, i, hi = 0, 0, len(a) - 1
    while i <= hi:
        if a[i] < pivot:
            a[lo], a[i] = a[i], a[lo]
            lo += 1
            i += 1
        elif a[i] > pivot:
            a[i], a[hi] = a[hi], a[i]
            hi -= 1              # i НЕ увеличиваем: пришедший справа элемент не просмотрен
        else:
            i += 1
    return lo, hi + 1

Тонкость, на которой спотыкаются все: в ветке a[i] > pivot указатель i остаётся на месте, потому что элемент, прилетевший из хвоста, ещё не классифицирован. Это же разбиение используется в quicksort для устойчивости к массивам с большим числом равных ключей — подробнее в статье Сортировки.

4. Скользящее окно: главная идея

Переходим к самому мощному варианту. Задача обычно звучит так: найти оптимальный (самый длинный / самый короткий) непрерывный подотрезок, удовлетворяющий условию P.

Наивно: перебрать все n(n+1)/2 подотрезков. Окно превращает это в один проход.

4.1 Условие применимости — сформулируем строго

Пусть P(l, r) — предикат «подотрезок a[l..r] допустим».

Определение. Предикат P называется наследственным вниз (downward-closed), если из P(l, r) следует P(l', r') для любого вложенного отрезка l ≤ l' ≤ r' ≤ r. Иначе говоря: если окно допустимо, то любое его подокно тоже допустимо.

Теорема. Если P наследственный вниз, то функция f(r) = min { l : P(l, r) } (минимальная левая граница допустимого окна, кончающегося в r) не убывает по r.

Доказательство. Пусть от противного f(r+1) < f(r) для некоторого r. Обозначим l₀ = f(r+1), то есть P(l₀, r+1) истинно. Отрезок [l₀, r] вложен в [l₀, r+1], значит по наследственности P(l₀, r) тоже истинно. Но l₀ < f(r), что противоречит минимальности f(r). ∎

Именно эта теорема — вся математика скользящего окна. Из неё следует: при увеличении r левую границу никогда не нужно возвращать назад, поэтому l тоже монотонен, и оба указателя суммарно делают не более 2n шагов.

Примеры наследственных предикатов:

4.2 Шаблон переменного окна

Три обязательные операции, которые надо спроектировать до кода:

1. add(x) — включить элемент в состояние окна за O(1) (или O(log n));
2. remove(x) — исключить элемент за ту же цену;
3. valid() — проверить предикат по состоянию, не пробегая окно заново.

Если remove реализовать нельзя (состояние необратимо — например, вы храните только максимум в переменной), простое окно не работает: нужен монотонный дек (§6) или техника «два стека» / «окно из двух указателей с пересчётом» (§6.3).

4.3 Жизненный цикл окна

5. Рабочие реализации

5.1 Фиксированное окно: скользящая сумма

Простейший случай — длина окна задана. Пересчитывать сумму каждый раз — O(nk); инкрементально — O(n):

def max_sum_fixed(a: list[int], k: int) -> int:
    """Максимальная сумма окна длины k. O(n) времени, O(1) памяти."""
    if len(a) < k:
        raise ValueError("массив короче окна")
    s = sum(a[:k])
    best = s
    for r in range(k, len(a)):
        s += a[r] - a[r - k]     # вошёл a[r], вышел a[r-k]
        best = max(best, s)
    return best

Численная ловушка: для float инкрементальное «прибавили–вычли» накапливает ошибку округления, и после миллиона шагов скользящее среднее может заметно уехать. В финтех-коде и в обработке сигналов либо считают в Decimal/целых «копейках», либо периодически пересчитывают сумму окна с нуля, либо применяют компенсированное суммирование Кэхэна.

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

def longest_unique(s: str) -> int:
    """Длина самой длинной подстроки без повторяющихся символов.
    O(n) времени, O(min(n, |Σ|)) памяти."""
    last: dict[str, int] = {}     # символ -> его последний индекс
    l, best = 0, 0
    for r, ch in enumerate(s):
        if ch in last and last[ch] >= l:
            l = last[ch] + 1      # прыжок сразу за прошлое вхождение
        last[ch] = r
        best = max(best, r - l + 1)
    return best

Здесь l двигается не по одному, а прыжком — но по-прежнему только вправо, поэтому суммарная работа остаётся линейной. Условие last[ch] >= l критично: без него левая граница может «откатиться» на устаревшее вхождение, уже выпавшее из окна.

5.3 Переменное окно с накоплением дефицита: минимальное окно-покрытие

Найти кратчайшую подстроку s, содержащую все символы t с учётом кратностей. Здесь предикат «окно покрывает t» наследственный вверх, а не вниз, поэтому шаблон зеркальный: расширяем до допустимости, затем сжимаем, пока допустимо.

from collections import Counter

def min_window(s: str, t: str) -> str:
    """Кратчайшее окно s, покрывающее мультимножество t.
    O(|s| + |t|) времени, O(|Σ|) памяти."""
    if not t or len(s) < len(t):
        return ""
    need = Counter(t)
    missing = len(t)              # сколько «единиц покрытия» ещё не хватает
    l = 0
    best = (float("inf"), 0, 0)

    for r, ch in enumerate(s):
        if need[ch] > 0:          # символ реально закрывает дефицит
            missing -= 1
        need[ch] -= 1             # отрицательные значения = излишек

        while missing == 0:       # окно допустимо — жмём слева
            if r - l + 1 < best[0]:
                best = (r - l + 1, l, r)
            left = s[l]
            need[left] += 1
            if need[left] > 0:    # сняли необходимый символ — покрытие сломалось
                missing += 1
            l += 1

    return "" if best[0] == float("inf") else s[best[1]:best[2] + 1]

Приём с missing вместо посимвольного сравнения счётчиков — то, что превращает O(n·|Σ|) в O(n). Хранить «сколько единиц не хватает» одним числом дешевле, чем каждый раз сравнивать две хеш-таблицы.

5.4 Тот же шаблон на Go

Полезно увидеть окно без словарей — на массиве-счётчике, когда алфавит фиксирован:

// LongestAtMostK возвращает длину самого длинного подотрезка,
// содержащего не более k различных байт. O(n) времени, O(256) памяти.
func LongestAtMostK(s []byte, k int) int {
    var cnt [256]int
    distinct, l, best := 0, 0, 0

    for r := 0; r < len(s); r++ {
        if cnt[s[r]] == 0 {
            distinct++
        }
        cnt[s[r]]++

        for distinct > k { // сжимаем, пока предикат нарушен
            cnt[s[l]]--
            if cnt[s[l]] == 0 {
                distinct--
            }
            l++
        }

        if r-l+1 > best {
            best = r - l + 1
        }
    }
    return best
}

Фиксированный массив вместо map — это не микрооптимизация: разница на горячем пути легко достигает 5–10×, потому что массив на 1 КБ целиком живёт в L1-кэше и не требует хеширования. Подробнее о таких эффектах — в статье Практическая оптимизация.

6. Когда состояние необратимо: монотонный дек

Задача sliding window maximum: для каждого окна длины k вывести максимум. Здесь remove не выражается через переменную-максимум — узнав, что из окна вышел текущий максимум, мы не знаем нового, не пересканировав окно.

Решение — хранить в деке индексы кандидатов на будущий максимум в порядке убывания значений. Элемент, который меньше только что пришедшего и стоит левее него, никогда больше не станет максимумом ни одного окна — его можно выбросить навсегда.

from collections import deque

def sliding_max(a: list[int], k: int) -> list[int]:
    """Максимум каждого окна длины k. O(n) времени, O(k) памяти."""
    dq: deque[int] = deque()   # индексы, значения по ним строго убывают
    res = []
    for r, x in enumerate(a):
        while dq and a[dq[-1]] <= x:
            dq.pop()           # хвост побеждён и больше не нужен
        dq.append(r)
        if dq[0] <= r - k:
            dq.popleft()       # голова вышла за левую границу окна
        if r >= k - 1:
            res.append(a[dq[0]])
    return res

Анализ. Внутренний while выглядит вложенным циклом, но каждый индекс добавляется в дек ровно один раз и удаляется не более одного раза. Формально: потенциал Φ = |dq| неотрицателен, каждая итерация внешнего цикла увеличивает его максимум на единицу, а pop уменьшает. Суммарное число pop ≤ суммарное число push = n. Итого O(n) времени и O(k) памяти.

6.1 Общий рецепт «окно + структура»

Когда предикат не выражается через O(1)-обратимое состояние, окно комбинируют со структурой данных. Стоимость шага перестаёт быть константной, но остаётся логарифмической:

Техника «двух стеков» (sliding window aggregation) заслуживает отдельного упоминания: она реализует очередь через два стека с накопленными агрегатами и даёт амортизированно O(1) для любой ассоциативной операции — max, gcd, побитовое AND, конкатенация матриц. Каноническое изложение — статья «Optimal and General Out-of-Order Sliding-Window Aggregation» (VLDB 2019), а практическое — раздел про очередь с минимумом в Algorithms for Competitive Programming.

6.2 Отрицательные числа: чем заменить окно

Классика: «сколько подотрезков имеют сумму ровно S». При наличии отрицательных чисел предикат не монотонен, окно неприменимо. Рабочая замена — префиксные суммы + хеш-таблица:

from collections import defaultdict

def count_subarrays_with_sum(a: list[int], S: int) -> int:
    """Число подотрезков с суммой ровно S. Работает с отрицательными.
    O(n) времени, O(n) памяти."""
    seen = defaultdict(int)
    seen[0] = 1               # пустой префикс
    prefix, count = 0, 0
    for x in a:
        prefix += x
        count += seen[prefix - S]   # сколько левых границ дают нужную сумму
        seen[prefix] += 1
    return count

Разменяли O(1) памяти на O(n), зато сняли требование монотонности. Это самая частая корректная альтернатива окну, и её стоит держать в голове как «план Б».

7. Типичные ошибки

1. Применили окно к немонотонному предикату. Самый опасный класс: код проходит примеры из условия и врёт на некоторых входах. Проверка: выполняется ли наследственность из §4.1? Если предикат содержит «ровно», «сумма с отрицательными», «максимум минус минимум ≥ …» — почти наверняка нет.

2. «Ровно k различных» через одно окно. Правильный приём — разность двух окон: exactly(k) = atMost(k) - atMost(k-1). Каждая половина монотонна, разность даёт ответ.

3. Обновление ответа не в том месте. Для «самого длинного допустимого» ответ обновляется после восстановления допустимости; для «самого короткого допустимого» — внутри цикла сжатия. Перепутать эти две точки — самая частая причина ответа, отличающегося на единицу.

4. Забыли, что while сжатия может опустошить окно. Условие цикла должно быть while l <= r and ..., иначе l перескочит r и длина станет отрицательной.

5. Возврат левой границы назад. Любое l -= 1 или l = 0 внутри цикла ломает амортизацию и превращает алгоритм в O(n²) — либо, что хуже, зацикливает его.

6. Целочисленное переполнение суммы окна. В Go, Java, C++ сумма int32 на длинном окне переполняется молча. В Python проблемы нет, что делает Python-прототип обманчиво безопасным при последующем переписывании.

7. Двойной учёт при l и r на одной позиции. В задачах на пары обязательно l < r, а не l <= r: иначе элемент складывается сам с собой.

8. Забыли отсортировать вход. Встречные указатели на неотсортированном массиве не падают — они возвращают неправильный ответ. Стоит добавить assert или хотя бы комментарий о предусловии.

8. Сложность и trade-offs

Практические соображения при выборе:

• Память против предусловий. Хеш-подход не требует сортировки, но берёт O(n) памяти и проигрывает по константе. На массиве, который уже отсортирован (типичная ситуация для постинг-листов, временных рядов, отсортированных индексов БД), два указателя выигрывают в разы за счёт последовательного доступа и предсказуемых ветвлений.
• Кэш-дружелюбность. Оба указателя движутся линейно — идеальный паттерн для аппаратного префетчера. Это часто важнее асимптотики: линейный проход по массиву на порядок быстрее теоретически равного по сложности обхода хеш-таблицы.
• Онлайн-режим. Скользящее окно естественно работает потоково: чтобы обработать элемент, нужно только состояние окна, а не весь массив. Это делает приём базовым в потоковой обработке — см. Потоковые алгоритмы.
• Границы применимости. Если требуется не подотрезок, а подпоследовательность (элементы не подряд), окно не поможет — это уже территория динамического программирования.

9. Как это применяют в проде

Приём выглядит «олимпиадным», но на самом деле встречается в инфраструктурном коде постоянно.

9.1 TCP: скользящее окно как протокол

Флоу-контроль TCP — буквально скользящее окно: отправитель держит окно неподтверждённых байт, правая граница двигается при отправке, левая — при получении ACK.

Ровно та же пара границ, только «допустимость» задаётся не предикатом на данных, а объявленным размером буфера получателя. Первоисточник — RFC 9293, раздел 3.8, современная замена RFC 793.

9.2 Rate limiting

Ограничители запросов «N в минуту» реализуются двумя вариантами окна:

• Sliding window log — дек таймстемпов, при каждом запросе выбрасываем всё старше now - T (левая граница) и проверяем длину. Точно, но память O(N) на клиента.
• Sliding window counter — два соседних фиксированных счётчика с линейной интерполяцией. Память O(1), погрешность несколько процентов. Именно так работает ограничитель в Cloudflare, описание — How we built rate limiting capable of scaling to millions of domains.

from collections import deque
import time

class SlidingWindowLimiter:
    """Разрешает не более limit событий за window секунд. O(1) амортизированно."""
    def __init__(self, limit: int, window: float):
        self.limit, self.window = limit, window
        self.events: deque[float] = deque()

    def allow(self, now: float | None = None) -> bool:
        now = time.monotonic() if now is None else now
        # левая граница окна: выбрасываем всё, что старше window
        while self.events and self.events[0] <= now - self.window:
            self.events.popleft()
        if len(self.events) < self.limit:
            self.events.append(now)
            return True
        return False

9.3 Компрессия

LZ77 и все его наследники (DEFLATE, gzip, zstd, LZ4) ищут повторы в скользящем окне последних N байт — 32 КБ в DEFLATE, до сотен мегабайт в zstd с длинным режимом. Размер окна и есть главный компромисс «степень сжатия против памяти». См. RFC 1951 и документацию zstd.

9.4 Потоковая аналитика

Оконные агрегаты в Flink, Kafka Streams и Spark Structured Streaming (tumbling, sliding, session windows) — тот же приём, поднятый до уровня фреймворка: состояние окна, функции добавления и выселения, watermark вместо простого индекса. См. Flink Windows. Про потоковые пайплайны есть отдельный трек — см. курс по data engineering на портале.

9.5 Поиск и базы данных

Слияние отсортированных постинг-листов в инвертированном индексе — два указателя по двум массивам. merge join в СУБД — то же самое над отсортированными потоками строк. Кстати, и git merge по diff-хунтам, и rsync c его rolling checksum по скользящему окну — всё из этого семейства. Rolling-хеш окна — основа алгоритма Рабина–Карпа, см. Строковые алгоритмы.

9.6 Мониторинг и SRE

Скользящие перцентили латентности, скользящее среднее error rate, burn rate по SLO за окна 1 час и 6 часов — всё это окна с выселением; см. Google SRE Workbook.

10. Как распознать задачу за 30 секунд

Дополнительный сигнал: если в условии есть слова «минимальная длина», «максимальная длина», «не более k», «все различные», «непрерывный» — это почти всегда окно. Если «ровно k» — это разность двух окон. Если «сумма ровно S» с отрицательными — это префиксные суммы.

Отдельно отметим родственный приём: бинарный поиск по ответу часто комбинируется с окном — фиксируем длину L, проверяем за O(n) окном, существует ли допустимое окно длины L, и бинарно ищем максимальное такое L. Работает, когда монотонности по l нет, но есть монотонность по длине. Подробнее — Поиск и бинарный поиск.

11. Мини-практикум

Задачи покрывают все схемы статьи; решать стоит, проговаривая инвариант вслух.

1. Сумма двух в отсортированном; валидный палиндром с пропуском не-букв — встречные указатели.
2. Container with most water — встречные указатели с аргументом отбрасывания.
3. Самая длинная подстрока без повторов; «фрукты в две корзины» — окно со счётчиком.
4. Минимальное окно-покрытие; минимальная длина подотрезка с суммой ≥ S при a[i] > 0 — окно на сжатие.
5. Подотрезки ровно с k различными — разность двух окон.
6. Максимум скользящего окна — монотонный дек.
7. Подотрезки с суммой ровно S при отрицательных — чтобы почувствовать, где окно ломается.

Подборки с разбором: CSES Problem Set (Sorting and Searching), USACO Guide — Two Pointers, LeetCode Sliding Window.

12. Источники

• Кормен, Лейзерсон, Ривест, Штайн. Introduction to Algorithms, 4-е изд. — амортизационный анализ (гл. 16), метод потенциалов, инварианты цикла (гл. 2).
• Стивен Скиена. The Algorithm Design Manual, 3-е изд. — практический разбор приёмов на массивах, сайт книги.
• Антти Лааксонен. Competitive Programmer’s Handbook — глава 8 целиком про два указателя, свободно доступна: cses.fi/book/book.pdf.
• cp-algorithms.com — минимум в очереди / стеке — монотонные структуры и техника двух стеков.
• Tangwongsan, Hirzel, Schneider. Optimal and General Out-of-Order Sliding-Window Aggregation, VLDB 2019 — PDF.
• Grønlund, Pettie. Threesomes, Degenerates, and Love Triangles — arXiv:1404.0799.
• RFC 9293 — Transmission Control Protocol — скользящее окно как механизм флоу-контроля.
• Apache Flink — Windows — оконные агрегаты в потоковой обработке.

Итог

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

Чек-лист перед тем, как писать код:

1. Что ищем — пару по значению или непрерывный подотрезок?
2. Что монотонно: целевая функция по индексу или предикат по вложенности?
3. Каков инвариант и какое множество кандидатов отбрасывает каждый шаг?
4. Обратимо ли состояние окна — есть ли дешёвый remove?
5. Где обновляется ответ — после восстановления допустимости или внутри сжатия?
6. Что будет на пустом входе, на одном элементе, на массиве из одинаковых значений?

Есть ответ на все шесть — реализация займёт десять строк и заработает с первого раза. Нет ответа хотя бы на один — почти гарантированно получится код, который выглядит правильным и незаметно врёт на части входов.

Что дальше

Указатели убирают лишний цикл там, где задача устроена «плоско» — вдоль одного массива. Но огромный класс задач устроен рекурсивно: решение целого выражается через решения частей. Следующая статья — про то, как это формализовать и во что превращается сложность при разбиении задачи пополам: Рекурсия и разделяй-и-властвуй.