Алгоритм скользящего окна в Go

Алгоритм скользящего окна позволяет эффективно обрабатывать подотрезки последовательности без лишних пересчётов. В этой статье объясняется идея, показана реализация на Go, разобраны сложность, случаи, когда метод не годится, тесты и контрольный список для внедрения.

Синий талисман Go (гопер) на фоне окна с горным пейзажем.

В программировании часто нужно получать информацию о фиксированных или меняющихся участках массива или строки — сумма, количество уникальных элементов, максимальная/минимальная комбинация и т. п. Алгоритм скользящего окна (sliding window) — это шаблон, который помогает решать такие задачи за линейное время, проходя по данным один раз.

Что такое скользящее окно — простая идея

Кратко: поддерживайте границы «окна» (начало и конец) и обновляйте агрегат (сумму, счётчик, частоты) при сдвиге окна, вместо того чтобы пересчитывать значение заново для каждого нового подотрезка.

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

Иллюстрация скользящего окна размером 3 на наборе чисел, с шагом вправо.

Окно может быть фиксированного размера (k) или динамически расширяться и сжиматься в зависимости от условий задачи.

Пример задачи: максимальная сумма подмассива длины k

Задача: дан массив nums и целое положительное k — найти максимальную сумму подряд идущих k элементов.

Идея решения:

Вычислите сумму первых k элементов — это начальное окно.
Затем сдвигайте окно вправо на один элемент: добавьте новый элемент справа и вычтите элемент слева.
После каждого сдвига обновляйте максимум, если текущая сумма больше.

Этот подход выполняет O(n) операций и O(1) дополнительной памяти.

Реализация на Go (полный, запускаемый пример)

package main

import "fmt"

func maximumSubarraySum(nums []int, k int) int {
    if k <= 0 || k > len(nums) {
        return 0 // простая защита: можно изменить на ошибку при необходимости
    }

    var windowStart, windowEnd, maxSum, windowSum int
    windowStart = 0

    // сумма первого окна
    for i := 0; i < k; i++ {
        windowSum += nums[i]
    }

    maxSum = windowSum

    for windowEnd = k; windowEnd < len(nums); windowEnd++ {
        windowSum = windowSum + nums[windowEnd] - nums[windowStart]

        if windowSum > maxSum {
            maxSum = windowSum
        }

        // сдвигаем начало окна вправо
        windowStart++
    }

    return maxSum
}

func main() {
    nums := []int{1, 5, 4, 8, 7, 1, 9}
    k := 3
    fmt.Println(maximumSubarraySum(nums, k)) // выведет 19
}

Краткий разбор кода:

Инициализируем windowSum суммой первых k элементов.
В цикле добавляем элемент справа (nums[windowEnd]) и вычитаем nums[windowStart].
Обновляем maxSum и сдвигаем windowStart.

Сложность

Временная: O(n) — один проход по массиву.
Память: O(1) дополнительной памяти (не считая входа).

Важно: если нужно не только значение суммы, но и сами индексы подмассива, отслеживайте индекс начала лучшего окна.

Когда метод работает и когда не подходит

Когда уместен:

Фиксированный размер окна (k).
Агрегаты, разрешающие учёт при добавлении/удалении (сумма, счётчики, максимум при использовании монолитной структуры и т.п.).

Когда не годится:

Если операция не поддерживает “отнятие” левого элемента (например, медиана без структуры данных для динамического поддержания упорядочения).
Если требуется выполнять сложные несворачиваемые агрегаты (например, специфическая статистика, которую сложнее обновлять при удалении элемента).
Для задач с многочисленными случайными доступами и зависимостями между элементами окно может не помочь.

Альтернативы:

Деревья поиска или балансированные BST / multiset для динамической медианы.
Дека/очередь для задач, где нужно быстро доставать и вставлять по обеим сторонам.
Префиксные суммы (prefix sums) — если нужно быстро вычислять суммы любых подотрезков за O(1) но с предварительной O(n) подготовкой.

Практические советы и эвристики

Всегда проверяйте граничные случаи: k <= 0, k > len(nums), пустой массив.
Если нужен индекс лучшего окна, запомните windowStart при каждом обновлении maxSum.
Для задач со строками и уникальностью символов используйте map[byte]int или map[rune]int для подсчёта частот внутри окна.

Ментальная модель: представьте, что окно — это «сканер» длины k, который вы катите по массиву, всегда обновляя только то, что изменилось.

Тесты и критерии приёмки

Критерии приёмки:

Функция возвращает корректную сумму для k в пределах [1, len(nums)].
Для кромочных случаев (k == len(nums]) функция возвращает сумму всего массива.
Для невалидного k (<=0 или >len(nums)) поведение заранее определено (в примере возвращаем 0).
Время выполнения растёт линейно с длиной входа.

Примеры юнит-тестов (псевдокод):

nums=[1,2,3,4], k=2 → expected=7 (3+4)
nums=[-1,-2,-3], k=1 → expected=-1
nums=[5,5,5,5], k=4 → expected=20
nums=[], k=0 → expected=0 (или ошибка)
nums=[1,2,3], k=5 → expected=0 (или ошибка)

Дополнительные сценарии и расширения

Отслеживание индексов лучшего окна:

// при обновлении maxSum запомнить start
if windowSum > maxSum {
    maxSum = windowSum
    bestStart = windowStart
}

Динамическое окно (переменная длина) — часто используется, когда нужно найти минимальную длину подотрезка, удовлетворяющего условию (например, сумма >= s). В этом случае при достижении условия сдвигаем начало окна, пытаясь сократить длину.
Подсчёт количества различных элементов в окне — используйте map и счётчик уникальных ключей.

Роль-based чеклист для команды

Для разработчика:

Написать функцию, покрыть граничные случаи.
Добавить комментарии и тесты.

Для рецензента:

Проверить сложность и память.
Проверить обработку крайних значений k.

Для архитектора:

Оценить применимость подхода к задаче (есть ли “отнимаемая” операция?).

Факто-бокс: ключевые числа

Временная сложность: O(n).
Дополнительная память: O(1) для классического варианта.
Подходит для массивов и строк длиной n, где n может достигать миллионов (при условии памяти и времени выполнения).

Частые ошибки и обходные ситуации

Попытка использовать скользящее окно для агрегатов, которые нельзя скорректировать при удалении элемента.
Неправильная инициализация окна (например, забыть заполнить windowSum первыми k элементами).
Необработанные граничные случаи (k==0, k>len(nums)).

Глоссарий — одно предложение на термин

windowStart / windowEnd: индексы начала и конца текущего окна.
windowSum: агрегат (например, сумма) для текущего окна.
k: фиксированный размер окна.

Короткое резюме

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

Важно

Если требуется агрегат, который нельзя «отнять» при сдвиге (например, медиана без подходящей структуры), смотрите в сторону специализированных структур данных: дек, сбалансированные деревья, heap-двойки или multiset.