---
title: "Скользящее окно: как узнать приём в задаче и написать за O(n)"
url: https://algopath.pro/ru/blog/skolzyashchee-okno
language: ru
summary: "Два индекса идут вправо, между ними отрезок со счётчиком. Сигналы в условии, шаблон переменного окна, код на Python, разбор на примере и задача Minimum Window Substring."
updated: 2026-10-15
---

# Скользящее окно: как узнать приём в задаче и написать за O(n)

**Короткий ответ.** Скользящее окно это два индекса, левый и правый. Оба идут по массиву в одну сторону. Между ними лежит отрезок, и мы держим про него счётчик. Правый край расширяет окно, левый сжимает, когда условие нарушено. Так задачи «самый длинный подмассив с условием» решаются за O(n) вместо O(n²). Ниже сигналы, шаблон, код на Python и разбор.

 

## Что такое скользящее окно?

 

Окно это непрерывный отрезок массива или строки. Его задают два индекса: left и right. Всё, что между ними, лежит внутри окна.

 

Окно бывает фиксированным: длина задана, и оно просто едет вправо. И бывает переменным: длина меняется по условию. Второй вид встречается чаще и сложнее.

 

Главное свойство: оба индекса только растут. Каждый элемент входит в окно один раз и выходит один раз. Поэтому весь проход стоит O(n).

 

## По каким словам в задаче узнать скользящее окно?

 

- «Самая длинная подстрока без повторов».
- «Наименьший подмассив с суммой не меньше k».
- «Максимальная сумма k подряд идущих элементов».
- «Есть ли перестановка строки s внутри строки t».

 

Общий признак: речь о непрерывном отрезке. У отрезка есть свойство, которое легко обновить при сдвиге края. Если отрезок может быть не непрерывным, окно не подходит.

 

## Как устроен шаблон переменного окна?

 

- left = 0. Идём right от 0 до n - 1.
- Добавляем элемент right в счётчик.
- Пока условие нарушено, убираем элемент left из счётчика и двигаем left вправо.
- Теперь окно верное. Обновляем ответ его длиной или содержимым.

 

Внутренний while не делает проход квадратичным. left проходит массив один раз за всю работу.

 

## Как это выглядит на примере?

 

Строка «abcabcbb», ищем самую длинную подстроку без повторов. right на a, b, c: окно «abc», длина 3. right на второй a: повтор. Двигаем left, пока первая a не выйдет. Окно «bca».

 

right на второй b: повтор. left уходит за первую b. Окно «cab». right на второй c: окно «abc». right на третьей b: окно «cb». right на последней b: окно «b». Ответ 3.

 

## Как написать скользящее окно на Python?

 

```
def longest_unique(s):
    seen = set()
    left = best = 0
    for right, ch in enumerate(s):
        while ch in seen:            # условие нарушено
            seen.remove(s[left])
            left += 1
        seen.add(ch)
        best = max(best, right - left + 1)
    return best

def min_subarray_len(nums, target):
    left = total = 0
    best = float("inf")
    for right, x in enumerate(nums):
        total += x
        while total >= target:      # окно годится, пробуем сжать
            best = min(best, right - left + 1)
            total -= nums[left]
            left += 1
    return 0 if best == float("inf") else best
```

 

Во второй функции условие «пока годится» вместо «пока нарушено». Так ищут минимальное окно. Логика та же, меняется только знак.

 

## Чем скользящее окно отличается от двух указателей?

 

| Признак | Скользящее окно | Два указателя с концов |
| --- | --- | --- |
| Направление | Оба идут вправо | Идут навстречу |
| Что ищем | Непрерывный отрезок | Пару элементов |
| Нужна сортировка | Нет | Обычно да |
| Состояние | Счётчик по окну | Только два значения |
| Пример | Longest Substring Without Repeating | Two Sum II |

 

Ещё три пары, которые путают, и как вести их список, разобраны в статье [два указателя и скользящее окно](/ru/blog/dva-ukazatelya-i-skolzyashchee-okno).

 

## Как решить Minimum Window Substring?

 

Дана строка s и строка t. Нужно самое короткое окно в s со всеми буквами t. Кратность букв учитывается.

 

Считаем буквы t в словаре need. Двигаем right и уменьшаем need по букве. Заводим счётчик missing, сколько букв ещё не хватает. Когда missing равен нулю, окно годится. Сжимаем left, пока окно годится, и запоминаем лучшее.

 

Каждая буква входит и выходит один раз. Время O(|s| + |t|).

 

## Как решить задачу про максимальную сумму k подряд идущих?

 

Это фиксированное окно. Считаем сумму первых k элементов. Дальше на каждом шаге прибавляем новый элемент справа и вычитаем ушедший слева. Запоминаем максимум.

 

Пересчёт суммы с нуля на каждом шаге дал бы O(n · k). Окно даёт O(n). Это самый короткий пример, с которого стоит начинать объяснение.

 

## На каких ошибках ломается скользящее окно?

 

- Сбрасывают left в ноль при нарушении вместо сдвига на один. Получается O(n²).
- Обновляют ответ до того, как окно снова стало верным.
- Считают длину как right - left вместо right - left + 1.
- Берут окно для задачи про подпоследовательность, где элементы могут не идти подряд.

 

## Как объяснить приём на собеседовании?

 

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

 

Потом покажите наивное решение за O(n²). Скажите, что окно убирает пересчёт с нуля. Это и есть довод.

 

Отработать узнавание приёма можно на странице [скользящее окно](/ru/patterns/sliding-window-variable). Версия с фиксированной длиной лежит на странице [окно фиксированного размера](/ru/patterns/sliding-window-fixed).

 

## Вопросы и ответы

 

### Работает ли окно с отрицательными числами?

 

Для задач про сумму нет. Условие «сумма не меньше k» перестаёт быть монотонным. Тогда берут префиксные суммы с хеш-таблицей.

 

### Как хранить счётчик для строк?

 

Словарь буква в число или массив из 26 ячеек для латиницы. Массив быстрее, словарь универсальнее.

 

### Как понять, что задача про фиксированное окно?

 

В условии есть число k и слова «подряд идущих». Тогда окно всегда длины k, а left равен right - k + 1.

 

### Что делать, если условие про окно сложное?

 

Держите вспомогательную структуру. Для «не больше k разных букв» это словарь со счётчиками и его размер. Для «максимум в окне» это монотонная очередь. Само движение краёв не меняется.

 

### Где приём встречается в реальных системах?

 

В ограничителях запросов: сколько запросов пришло за последнюю минуту. В мониторинге: среднее по последним ста измерениям. Это то же окно, только по времени.