Что такое техника скользящего окна (sliding-window)?

Question

Accepted Answer

Техника **sliding-window** поддерживает смежный диапазон (окно) над массивом или строкой и скользит по нему вместо пересчета с нуля, решая множество задач с подмассивами/подстроками за **O(n)**.

## Идея

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

## Пример: максимальная сумма любого окна размером k

```python
def max_window_sum(arr, k):
    window = sum(arr[:k])       # sum of first window
    best = window
    for i in range(k, len(arr)):
        window += arr[i] - arr[i - k]  # add new, drop old
        best = max(best, window)
    return best

max_window_sum([2, 1, 5, 1, 3, 2], 3)  # -> 9 (5+1+3)
```

## Сложность

- **Время:** O(n) — каждый элемент входит и выходит из окна один раз.
- **Память:** O(1) для фиксированных окон, O(k) при отслеживании содержимого.

## Когда использовать / ошибки

Используйте для задач «самый длинный/самый короткий/максимальный подмассив со свойством X». Для **переменных** окон переместите левый указатель, чтобы восстановить ограничение. Остерегайтесь ошибок off-by-one при добавлении/удалении граничных элементов.

## Почему это важно

Скользящее окно исключает избыточную работу, превращая O(n·k) пересчет в один проход.

Это универсальный паттерн для задач с подстроками и подмассивами, которые постоянно встречаются на собеседованиях.

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