Скользящее окно в Go: пример и реализация

Голубой талисман языка Go на фоне окна с видом на горный пейзаж.

Краткое введение

В программировании часто требуется вычислять характеристики подотрезков последовательности: суммы, частоты, максимумы и т. д. Алгоритм скользящего окна поддерживает «окно» над последовательностью — одни и те же элементы не пересчитываются заново при смещении окна, что снижает лишние операции.

Демонстрация скользящего окна размером 3 в массиве чисел; на втором изображении окно сдвинуто на один шаг вперёд.

Важно: скользящее окно применимо, когда нужно работать с контiguous (смежными) подотрезками. Если требуется выбирать несмежные элементы, нужны другие подходы.

Понимание идеи

Ключевая идея: задать границы окна (начало и конец) и при сдвиге обновлять агрегат (например, сумму) инкрементально — добавить новый элемент, убрать устаревший. Для фиксированной длины k сначала вычисляют сумму первых k элементов, затем для каждого следующего индекса обновляют сумму: +nums[new] - nums[old].

Когда применять:

подсчёт суммы/среднего/максимума в скользящем подмассиве фиксированной длины k;
нахождение подстрок с заданными свойствами (например, ровно k символов с условием);
двухуказательный (двойной) указатель для вариативного окна (менее жёсткий сценарий: длина окна не фиксирована).

Реализация в Go — пример: максимальная сумма подмассива длины k

Мы используем стандартную задачу: найти подмассив длины k с наибольшей суммой. Функция принимает nums []int и k int и возвращает int.

nums := []int{1, 5, 4, 8, 7, 1, 9}

k := 3

func maximumSubarraySum(nums []int, k int) int {  
    // body  
}

Первый шаг — сумма первых k элементов:

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  
    }  
  
    // slide window forward  
    windowStart++  
}

И возвращаем результат:

return maxSum

Полная функция (как в исходнике):

func maximumSubarraySum(nums []int, k int) int {  
    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  
        }  
  
        // slide window forward  
        windowStart++      
    }  
  
    return maxSum  
}

Тест в main:

func main() {  
    nums := []int{1, 5, 4, 8, 7, 1, 9}  
    k := 3  
    fmt.Println(maximumSubarraySum(nums, k))  
}

Вывод: 19 (подмассив [4, 8, 7]).

Пошаговое объяснение на примере

Дано nums = [1,5,4,8,7,1,9], k = 3

windowSum = 1 + 5 + 4 = 10, maxSum = 10
Сдвиг: убрать 1, добавить 8 → windowSum = 10 - 1 + 8 = 17, maxSum = 17
Сдвиг: убрать 5, добавить 7 → windowSum = 17 - 5 + 7 = 19, maxSum = 19
Сдвиг: убрать 4, добавить 1 → windowSum = 19 - 4 + 1 = 16, maxSum = 19
Сдвиг: убрать 8, добавить 9 → windowSum = 16 - 8 + 9 = 17, maxSum = 19

Итог: максимальная сумма — 19.

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

Временная сложность: O(n), где n = len(nums). Каждый элемент массива обрабатывается один раз.
Память: O(1) — дополнительная память постоянна (пара переменных для окна и суммы).

Факт: скользящее окно позволяет заменить наивные O(n*k) решения для фиксированного k.

Когда метод не применим или даёт неверный результат

Если вам нужны несмежные подмножества — используйте динамическое программирование, комбинаторные методы или жадные алгоритмы, в зависимости от задачи.
Для задач типа «максимальная сумма подмассива любой длины» лучше подходит алгоритм Кэдэйна (Kadane), а не фиксированное окно.
Если k > len(nums) — поведение нужно определить заранее (например, вернуть 0 или ошибку).
При наличии переполнения типов (очень большие значения сумм) — используйте более широкий тип (int64) или проверяйте переполнение.

Альтернативные подходы

Префиксные суммы: можно посчитать массив префиксных сумм и вычислять сумму любого подмассива за O(1). Это даёт O(n) на подготовку и O(1) на каждый запрос, но для одной проходной задачи скользящее окно проще и экономнее по памяти.
Алгоритм Кэдэйна: для поиска максимальной суммы подмассива любой длины.
Деревья отрезков или BIT: для динамических задач с частыми изменениями и запросами по сумме диапазона.

Шпаргалка и рекомендации при имплементации

Проверяйте валидность входных данных: len(nums) >= k > 0.
Для отрицательных чисел алгоритм работает одинаково; важно корректно инициализировать maxSum (например, суммой первых k элементов), а не нулём.
При работе с большими числами используйте int64.
Комментируйте смысл переменных: windowStart, windowEnd, windowSum.

Краткая таблица:

Идея: сдвиг окна + инкрементальное обновление агрегата
Время: O(n)
Память: O(1)
Применяется для: суммы, максимумов, подсчёта частот в подотрезках

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

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

Функция корректно возвращает максимальную сумму для len(nums) >= k.
Обработка граничных случаев: k == len(nums), k == 1, отрицательные числа, одинаковые элементы.
Стабильность при больших n (производительность O(n)).

Примеры тестов:

nums=[1,5,4,8,7,1,9], k=3 → 19
nums=[-2,-3,-1], k=2 → -3 (подмассив [-2,-1]? зависит от индексов — корректный ответ: максимальная сумма двух подряд элементов = -3)
nums=[5], k=1 → 5
nums=[2,2,2,2], k=3 → 6
k > len(nums) → явная ошибка или предопределённый ответ (зависит от требований)

Рольные чек-листы

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

Проверка входных данных
Инициализация суммы первых k элементов
Правильный цикл с windowEnd = k
Тесты на граничные случаи

Для ревьюера:

Время выполнения — линейное
Отсутствие лишнего копирования подмассивов
Обработка переполнения

Для тестировщика производительности:

Запустить на входе с n ≥ 10^6 при разных распределениях чисел
Проверить потребление памяти

Mental models и эвристики

Представляйте окно как «очередь» индексов: при добавлении элемента добавляете в хвост, при сдвиге — удаляете из головы.
Вместо явного копирования среза нужно обновлять агрегат: add(new) - remove(old).
Если агрегат не поддерживает обратной операции (например, медиана), придётся использовать более сложные структуры (две кучи, multiset).

Быстрый чеклист миграции для других языков

Python: можно использовать deque или просто индексы с суммой.
Java: массивы и циклы; при необходимости HashMap для частот внутри окна.
C++: vector и два указателя; для медианы — два multiset/heap.

Мини-руководство при инцидентах (rollback)

Если новая реализация вызывает регресс:

Откатить до стабильного коммита.
Запустить пакет тестов (включая нагрузки).
Проанализировать случай, где сумма отличается — проверить переполнение и граничные случаи.
Ввести дополнительную проверку входных данных.

Глоссарий (1 строка)

windowStart: индекс начала окна.
windowEnd: индекс элемента, добавляемого при сдвиге (обычно i).
windowSum: текущая сумма элементов в окне.
maxSum: наибольшая найденная сумма окна.
k: фиксированная длина окна.

Принципиальная блок-схема решений (Mermaid)

flowchart TD
  A[Start] --> B{len'nums' >= k?}
  B -- No --> C[Return error / special value]
  B -- Yes --> D[Compute sum of first k elements]
  D --> E[Iterate i from k to len'nums'-1]
  E --> F[windowSum += nums[i] - nums[i-k]]
  F --> G{windowSum > maxSum?}
  G -- Yes --> H[maxSum = windowSum]
  G -- No --> I[continue]
  H --> I --> J[End loop]
  J --> K[Return maxSum]

Итоги

Скользящее окно — простой, но мощный приём для задач на последовательностях. Для фиксированного k он даёт линейную сложность и постоянное дополнительное пространство. Важны проверки входных данных, обработка граничных случаев и учет диапазонов типов при больших суммах.

Важно: выбирайте альтернативы (префиксные суммы, Кэдэйн, деревья отрезков) в зависимости от требований задачи.