Sliding Window: Скользящее окно

Цели урока

• Понимать идею скользящего окна
• Решать задачи с фиксированным размером окна
• Применять переменное окно для оптимизации
• Комбинировать sliding window с HashMap
• Решать строковые задачи: анаграммы, уникальные символы

Предварительные знания

• Two Pointers
• Хеш-таблицы

• Two Pointers
• Хеш-таблицы

Sliding Window - один из самых частых паттернов на собеседованиях. LeetCode #3 (Longest Substring) - в топ-5 по популярности. Освоив эту технику, вы решите десятки задач.

• Сетевые протоколы: TCP sliding window
• Стриминг данных: скользящие агрегаты
• Финансы: moving average
• Мониторинг: rate limiting

Название, заимствованное из сетевых протоколов

Паттерн скользящего окна в алгоритмах, это фольклор, у него нет единственного автора, но у самого названия есть ясное происхождение в сетях. В 1970-х, когда Винт Серф и Роберт Кан проектировали TCP, им понадобилось управление потоком, чтобы быстрый отправитель не захлестнул медленного получателя. Решением, формализованным в RFC 793 в 1981 году, стал протокол скользящего окна: получатель сообщает, сколько байт он может принять, а отправитель держит окно неподтверждённых байт, которое сдвигается вперёд по мере прихода подтверждений. Курсы алгоритмов заимствовали этот образ напрямую. Непрерывный диапазон по массиву или строке трактуется как окно, чьи две границы движутся, так что каждый элемент входит и выходит не более одного раза, и наивный обход за O(n на k) превращается в O(n). Сетевая метафора прижилась, потому что точно передаёт суть: фиксированная или растущая рамка, движущаяся по потоку.

Идея скользящего окна

**Sliding Window** - техника для задач на подмассивы и подстроки. Вместо пересчёта с нуля - обновляем только края окна.

**Два типа окон:** фиксированного размера k и переменного размера (расширяется/сужается).

Окно фиксированного размера

**Задача: максимальная сумма подмассива длины k**

**Среднее в скользящем окне:**

Окно переменного размера

**Размер окна меняется динамически.** Расширяем пока условие выполняется, сужаем когда нарушается.

**Максимальный подмассив с суммой ≤ k:**

**Важно:** переменное окно работает когда добавление элементов монотонно влияет на условие (сумма растёт). Для отрицательных чисел - нужны другие подходы.

Строковые задачи

**Sliding window идеально подходит для задач на подстроки!**

**Longest Substring Without Repeating Characters:**

Sliding Window + HashMap

**Комбинация sliding window с хеш-таблицей - устойчивый паттерн.**

**Minimum Window Substring - сложная классика:**

**Паттерн:** HashMap хранит состояние окна, позволяя проверять условие за O(1).

Sliding Window

• Фиксированное окно: сумма/среднее подмассива длины k
• Переменное окно: расширяем и сужаем по условию
• Строки: подстроки с ограничениями на символы
• HashMap хранит состояние окна
• O(n) вместо O(n×k) или O(n²)

Связанные темы

Sliding Window - развитие идеи two pointers.

• Two Pointers — Базовая техника
• Хеш-таблицы — Хранение состояния окна
• Monotonic Queue — Оптимизация для min/max в окне

Связанные уроки

• alg-26-two-pointers — Окно - это два однонаправленных указателя
• ds-06-hash-intro — Переменные окна хранят содержимое в хеш-таблице
• ds-25-monotonic-stack — Монотонная очередь даёт максимум окна за O(1)
• alg-36-prefix-sum — Оба сводят повторную работу с диапазоном к O(1) за шаг
• stat-13-time-series