Скользящее окно: решаем задачи на подмассивы и подстроки без лишних циклов

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

Паттерн «скользящего окна» (sliding window) — один из фундаментальных приёмов алгоритмического мышления. Он не требует знания сложных структур данных и не предполагает математических откровений. Но он меняет способ думать о задачах на последовательностях. Разберём его честно: от идеи до конкретного кода, с типичными ошибками и нюансами.

Что такое скользящее окно и почему оно работает

Представьте, что вы читаете длинный текст и держите в голове только последние N слов. Когда вы переходите к следующему слову, вы не перечитываете всё с начала — вы просто добавляете новое слово и «забываете» самое старое. Это и есть скользящее окно.

Формально: мы поддерживаем некий «срез» массива или строки — диапазон индексов [left, right] — и двигаем его вправо, обновляя агрегированное состояние (сумму, множество символов, счётчик) инкрементально. Вместо того чтобы пересчитывать всё заново для каждой позиции, мы делаем одну операцию добавления и одну операцию удаления.

Ключевое условие применимости: задача должна обладать свойством монотонности или локальности. То есть ответ для окна [left+1, right] должен вычисляться из ответа для [left, right] за константное время. Если это условие выполнено — скользящее окно применимо.

Паттерн существует в двух вариантах:

• Фиксированный размер окна — размер k задан заранее, окно просто движется вправо.
• Переменный размер окна — правая граница расширяется, левая сжимается по условию. Этот вариант сложнее, но мощнее.

Задача 1: максимальная сумма подмассива фиксированной длины

Наивное решение и его цена

Классическая постановка: дан массив целых чисел, найти подмассив длины k с максимальной суммой.

def max_sum_naive(arr: list[int], k: int) -> int:
    n = len(arr)
    max_sum = float('-inf')
    
    for i in range(n - k + 1):
        current_sum = 0
        for j in range(i, i + k):  # вложенный цикл — O(k) на каждую позицию
            current_sum += arr[j]
        max_sum = max(max_sum, current_sum)
    
    return max_sum

Сложность: O(n × k). При k = n/2 это фактически O(n²). Для массива из 10⁶ элементов — порядка 10¹² операций. Неприемлемо.

Решение через скользящее окно

Заметим очевидное: сумма окна [i+1, i+k] отличается от суммы [i, i+k-1] ровно на два числа. Мы добавляем arr[i+k] и вычитаем arr[i]. Всё остальное остаётся неизменным.

def max_sum_sliding(arr: list[int], k: int) -> int:
    n = len(arr)
    if n < k:
        raise ValueError("Массив короче размера окна")
    
    # Считаем сумму первого окна
    window_sum = sum(arr[:k])
    max_sum = window_sum
    
    # Двигаем окно: добавляем правый элемент, убираем левый
    for i in range(k, n):
        window_sum += arr[i] - arr[i - k]
        max_sum = max(max_sum, window_sum)
    
    return max_sum

Сложность: O(n). Один проход по массиву, константная работа на каждом шаге.

Проверим:

arr = [2, 1, 5, 1, 3, 2]
k = 3
print(max_sum_sliding(arr, k))  # 9 (подмассив [2, 1, 5] → нет, [5, 1, 3] = 9)

Подмассивы: [2,1,5]=8, [1,5,1]=7, [5,1,3]=9, [1,3,2]=6. Ответ: 9. Верно.

Типичная ошибка

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

Задача 2: длиннейшая подстрока без повторяющихся символов

Это задача с переменным размером окна — и она значительно интереснее.

Постановка

Дана строка s. Найти длину наибольшей подстроки, в которой все символы уникальны.

Пример: "abcabcbb" → 3 (подстрока "abc").

Почему здесь нельзя использовать фиксированное окно

Мы не знаем заранее, какой длины будет ответ. Размер «правильного» окна меняется в зависимости от содержимого строки. Нужен другой подход.

Наивное решение: O(n²) или хуже

def longest_unique_naive(s: str) -> int:
    n = len(s)
    max_len = 0
    
    for i in range(n):
        seen = set()
        for j in range(i, n):
            if s[j] in seen:
                break
            seen.add(s[j])
            max_len = max(max_len, j - i + 1)
    
    return max_len

O(n²) в среднем, O(n³) в худшей реализации с проверкой подстроки через срез.

Решение через скользящее окно с хеш-множеством

Идея: расширяем правую границу right. Если s[right] уже есть в окне — сжимаем левую границу left до тех пор, пока дубликат не исчезнет.

def longest_unique_window(s: str) -> int:
    char_set = set()
    left = 0
    max_len = 0
    
    for right in range(len(s)):
        # Пока символ уже есть в окне — сжимаем слева
        while s[right] in char_set:
            char_set.remove(s[left])
            left += 1
        
        char_set.add(s[right])
        max_len = max(max_len, right - left + 1)
    
    return max_len

Сложность: O(n). Каждый символ добавляется в множество ровно один раз и удаляется не более одного раза. Суммарно — 2n операций.

print(longest_unique_window("abcabcbb"))  # 3
print(longest_unique_window("bbbbb"))     # 1
print(longest_unique_window("pwwkew"))    # 3 ("wke")
print(longest_unique_window(""))          # 0

Оптимизация через хеш-таблицу: O(n) без внутреннего while

Предыдущее решение формально O(n), но внутренний while может выполняться O(n) раз на одном шаге в худшем случае. Амортизированно всё равно O(n), но можно сделать чище — хранить не множество, а словарь с последней позицией каждого символа:

def longest_unique_optimized(s: str) -> int:
    last_seen = {}  # символ → последний индекс вхождения
    left = 0
    max_len = 0
    
    for right, char in enumerate(s):
        # Если символ уже видели И он внутри текущего окна
        if char in last_seen and last_seen[char] >= left:
            # Прыгаем левой границей сразу за предыдущее вхождение
            left = last_seen[char] + 1
        
        last_seen[char] = right
        max_len = max(max_len, right - left + 1)
    
    return max_len

Здесь нет внутреннего цикла вообще. Каждый символ обрабатывается ровно один раз. Проверка last_seen[char] >= left критически важна: без неё мы можем сдвинуть left назад, если символ встречался раньше текущего окна.

print(longest_unique_optimized("abba"))  # 2 ("ab" или "ba")
# Без проверки >= left: при 'a' на позиции 3 left сдвинулся бы на 1,
# хотя 'a' на позиции 0 уже вне окна [2, 3]

Когда скользящее окно не работает

Паттерн не универсален. Несколько случаев, где он неприменим или требует модификации:

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

Задачи с неаддитивными агрегатами. Если нужно поддерживать медиану или моду окна — простое добавление/удаление не даёт O(1) обновления. Здесь нужны более сложные структуры: упорядоченные множества, два heap'а.

Двумерные массивы. Скользящее окно расширяется на 2D, но требует дополнительной работы — например, предподсчёта сумм по столбцам.

Обобщённый шаблон переменного окна

Большинство задач с переменным окном укладываются в один шаблон:

def sliding_window_template(arr):
    left = 0
    state = ...      # текущее состояние окна (сумма, множество, счётчик)
    result = ...     # лучший найденный ответ
    
    for right in range(len(arr)):
        # 1. Расширяем окно: добавляем arr[right] в state
        state = update_add(state, arr[right])
        
        # 2. Сжимаем окно, пока условие нарушено
        while not is_valid(state):
            state = update_remove(state, arr[left])
            left += 1
        
        # 3. Обновляем результат для текущего валидного окна
        result = update_result(result, left, right, state)
    
    return result

Понимание этого шаблона позволяет быстро решать целый класс задач: минимальный подмассив с суммой ≥ target, подстрока, содержащая все символы из заданного набора (задача «Minimum Window Substring»), количество подмассивов с не более чем k различными элементами.

Именно такой подход — от абстрактного паттерна к конкретным задачам — используется в курсе «Алгоритмы и Структуры Данных на Python», где скользящее окно разбирается в контексте более широкой системы техник для работы с последовательностями.

Практика: задача на закрепление

Попробуйте самостоятельно реализовать следующее: дан массив положительных целых чисел arr и число target. Найти минимальную длину подмассива, сумма которого больше или равна target. Если такого подмассива нет — вернуть 0.

# Подсказка: используйте переменное окно.
# Расширяйте right, пока сумма < target.
# Как только сумма >= target — фиксируйте длину и сжимайте left.

def min_subarray_len(arr: list[int], target: int) -> int:
    left = 0
    current_sum = 0
    min_len = float('inf')
    
    for right in range(len(arr)):
        current_sum += arr[right]
        
        while current_sum >= target:
            min_len = min(min_len, right - left + 1)
            current_sum -= arr[left]
            left += 1
    
    return min_len if min_len != float('inf') else 0


print(min_subarray_len([2, 3, 1, 2, 4, 3], 7))  # 2 (подмассив [4, 3])
print(min_subarray_len([1, 1, 1, 1, 1], 11))     # 0

Обратите внимание на инверсию логики: здесь мы сжимаем окно не потому, что оно «плохое», а потому что хотим найти минимальное «хорошее».

Сложность и реальные числа

Чтобы не быть голословными — конкретные цифры. Пусть n = 10⁶:

Разница между O(n²) и O(n) на реальных данных — это разница между «программа зависла» и «программа ответила мгновенно».

Вывод

Скользящее окно — не трюк и не хак. Это способ мышления: вместо того чтобы пересчитывать всё с нуля, поддерживай инвариант и обновляй его инкрементально. Этот принцип встречается повсюду — в сетевых протоколах (TCP window), в обработке сигналов, в потоковых алгоритмах.

Освоить паттерн на уровне «применяю автоматически» можно только через практику. Начните с задач на LeetCode: #643 (Maximum Average Subarray), #3 (Longest Substring Without Repeating Characters), #76 (Minimum Window Substring) — они выстроены по нарастающей сложности и хорошо покрывают все варианты паттерна.

Если хочется разобраться с алгоритмическими техниками системно, а не по одной задаче за раз — курс «Алгоритмы и Структуры Данных на Python» даёт именно такой структурированный взгляд: от базовых паттернов до их применения в реальных задачах.

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