Скользящее окно (sliding window)

Окно растягивается и сжимается, проходя по массиву ровно один раз.

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

Идея приёма

Есть два вида окон: фиксированной ширины (сумма каждых k подряд) и переменной ширины (самая длинная подстрока без повторов). В обоих случаях правая граница расширяет окно, а левая сжимает, когда нарушается условие. Каждый элемент входит и выходит из окна максимум один раз — отсюда O(n).

Фиксированное окно: максимальная сумма k подряд

def max_sum_window(arr, k):
    window = sum(arr[:k])
    best = window
    for i in range(k, len(arr)):
        window += arr[i] - arr[i - k]
        best = max(best, window)
    return best

print(max_sum_window([2, 1, 5, 1, 3, 2], 3))
print(max_sum_window([1, 1, 1, 1], 2))

Вывод:

9
2

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

Дана строка, нужно найти длину самой длинной подстроки, в которой все символы различны. Расширяем окно вправо; если символ уже в окне — сдвигаем левую границу за его прошлое вхождение.

def longest_unique(s):
    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)
    return best

print(longest_unique("abcabcbb"))
print(longest_unique("bbbbb"))
print(longest_unique("pwwkew"))

Вывод:

3
1
3

Как работает под капотом

Ключ к O(n) — левая граница никогда не движется назад. И left, и right только увеличиваются, поэтому суммарно они делают не больше 2n шагов. Хеш last хранит последнюю позицию каждого символа, что позволяет за O(1) прыгнуть левой границей сразу за повтор, а не сдвигать её по одному. Условие last[ch] >= left важно: символ мог встречаться раньше, но уже вне текущего окна.

Частые ошибки

Двигать левую границу по одному символу вместо прыжка — это снова O(n^2).
Забыть проверку last[ch] >= left и ошибочно сжать окно из-за символа вне него.
Путать окно фиксированной и переменной ширины — у них разная логика сжатия.

Итог

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