Sliding Window

«Найдите самый короткий подотрезок с суммой не меньше S», «самую длинную подстроку без повторов», «максимальную сумму k подряд идущих» — во всех этих задачах наивное решение перебирает пары границ. Пар $O(n^2)$, и если внутри ещё и считать сумму заново, получается $O(n^3)$.

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

Правая граница идёт вперёд и пытается улучшить ответ. Левая двигается только тогда, когда окно перестало удовлетворять условию, и ровно настолько, чтобы оно снова стало допустимым. Возврата назад нет ни у одной из границ.

a:  2  3  1  2  4  3  1  2      цель: сумма >= 8

    [2  3  1  2]                сумма 8  -> длина 4
       [3  1  2  4]             сумма 10 -> длина 4
          [2  4  3]             сумма 9  -> длина 3
             [4  3  1]          сумма 8  -> длина 3

Восемь шагов правой границы и пять сдвигов левой — тринадцать операций вместо тридцати шести пар. Ответ: три элемента, например $2+4+3=9$.

left = 0
total = 0
best = inf

for right, x in enumerate(a):
    total += x                      # вошло в окно

    while total >= S:               # окно допустимо -- пробуем сжать
        best = min(best, right - left + 1)
        total -= a[left]            # вышло из окна
        left += 1

return 0 if best == inf else best

total = sum(a[:k])
best = total

for right in range(k, len(a)):
    total += a[right] - a[right - k]
    best = max(best, total)

• Время — $O(n)$: каждый индекс входит в окно один раз и выходит один раз.
• Память — $O(1)$ для суммы и $O(k)$ для счётчика символов, где $k$ — размер алфавита.
• Длина окна — right - left + 1; это выражение и есть место, где чаще всего ошибаются на единицу.

Корректность держится на монотонности. Для суммы неотрицательных чисел расширение окна вправо сумму только увеличивает, а сжатие слева — только уменьшает. Значит, для каждой правой границы существует ровно одна «пороговая» левая, и она не может оказаться левее пороговой для предыдущего шага: возвращать left назад никогда не нужно.

Отсюда же линейность, и она амортизированная, а не «по одному циклу»: вложенный while внутри for выглядит квадратично, но left за весь алгоритм сдвигается не более $n$ раз в сумме по всем итерациям.

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

• Отрицательные числа при условии на сумму. Монотонность исчезает, окно даёт неверный ответ; нужны префиксные суммы с хеш-таблицей.
• Длина окна. right - left + 1, а не right - left.
• Забыли вычесть уходящий элемент. Состояние окна разъезжается с самим окном, и ошибка проявляется только на длинных входах.
• `if` вместо `while` при сжатии. Одного сдвига левой границы часто недостаточно, чтобы окно снова стало допустимым.
• Пустой ответ. Когда допустимого окна нет вовсе, ответом должен быть ноль или «нет», а не начальное значение inf.

1. Почему вложенный while не делает решение квадратичным?
2. Максимальная сумма k подряд идущих — напишите обновление суммы за константу.
3. Самая длинная подстрока без повторяющихся символов: что хранится в состоянии окна?
4. Минимальный подотрезок с суммой не меньше S — а что изменится, если разрешить отрицательные числа?
5. Все анаграммы образца в строке: как сравнивать окно с образцом, не пересобирая счётчик?