Скользящее окно (фиксированный размер)

Скользящее окно (фиксированный размер): как это работает?

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

Теперь сдвиньте окно на одну ячейку вправо. Ровно один элемент входит и один выходит.

Обновите текущее значение по этим двум элементам. Прибавьте вошедший и вычтите вышедший.

Запишите ответ для этого окна до следующего сдвига. Лучший результат живёт в одной переменной.

Повторяйте, пока правый край не дойдёт до конца. Всего окон n минус k плюс один.

Ни одно окно не считается заново целиком. Именно это превращает O(nk) в O(n).

1. [4, 2, 7] сумма = 13Размер окна равен трём. Первое окно суммируется напрямую.
2. [2, 7, 1] сумма = 10Входит 1, выходит 4. Значит 13 плюс 1 минус 4 это 10.
3. лучшее = 13Это окно хуже первого. Лучший результат не меняется.
4. [7, 1, 5] сумма = 13Входит 5, выходит 2. Значит 10 плюс 5 минус 2 это 13.
5. ответ = 13Правый край дошёл до конца. Три окна, пять чтений.

function windowStat(arr, k) {
    let windowSum = 0;
    for (let i = 0; i < k; i++) windowSum += arr[i];
    let best = windowSum;
    for (let i = k; i < arr.length; i++) {
        windowSum += arr[i] - arr[i - k];
        best = Math.max(best, windowSum);
    }
    return best;
}

Скользящее окно (фиксированный размер): разбор примера

Найти все анаграммы слова

Даны строка s и более короткая строка p. Верните все начальные индексы, где в s стоит анаграмма p.

Анаграмма использует те же буквы в тех же количествах.

Посчитайте буквы p один раз. Потом катите окно такой же длины по строке s.

Каждый сдвиг добавляет одну букву и убирает одну. Сравните счётчики и при совпадении запишите индекс.

function findAnagrams(s, p) {
    if (p.length > s.length) return [];

    const need = new Array(26).fill(0);
    const have = new Array(26).fill(0);
    const at = (c) => c.charCodeAt(0) - 97;

    for (const c of p) need[at(c)]++;

    const result = [];
    for (let i = 0; i < s.length; i++) {
        have[at(s[i])]++;

        // one letter leaves as soon as the window is longer than p
        if (i >= p.length) have[at(s[i - p.length])]--;

        if (i >= p.length - 1 && need.every((n, j) => n === have[j])) {
            result.push(i - p.length + 1);
        }
    }

    return result;
}

Скользящее окно (фиксированный размер): когда применять?

Эти формулировки в условии ведут сюда:

• •непрерывный подмассив/подстрока заданной длины k
• •каждое окно размера k
• •скользящее среднее или скользящая сумма
• •мин/макс/количество/сумма по каждому фиксированному отрезку

Скользящее окно (фиксированный размер): с чем путают?

• Скользящее окно (переменное) (Sliding window (variable)): Переменное окно само выбирает ширину по условию. Это окно на всём проходе шириной k.
• Префиксные суммы (Prefix sums): Префиксные суммы строятся один раз и отвечают про любой диапазон. Окно отвечает про один движущийся отрезок.
• Монотонная дек-очередь (максимум/минимум окна) (Monotonic deque (sliding window max/min)): Сумма переживает вычитание, поэтому хватает арифметики. Максимуму нужна дек-очередь.
• Хеш-множество / словарь (Hash set / map): Словарь считает по всей коллекции и не знает позиций. Окно спрашивает только про k соседей.

Скользящее окно (фиксированный размер): частые ошибки

• Пересобирают окно на каждом шаге

  Суммирование k элементов в каждой позиции стоит O(nk). Используйте прошлый итог.

• Записывают ответ слишком рано

  Первые k минус одна позиций держат неполное окно. Начинайте запись, когда оно заполнилось.

• Убирают не тот элемент

  Выходящее значение стоит на индексе i минус k. Ошибка на единицу сдвигает все окна.

• Берут скользящую сумму ради максимума

  Вычитание вышедшего элемента максимум не восстановит. Для этого случая нужна монотонная дек-очередь.

Скользящее окно (фиксированный размер): задачи с собеседований

• Максимальная сумма подмассива длины k: Базовая форма: одно сложение и одно вычитание за шаг.
• Максимальное среднее подмассива I: Та же сумма, делённая на k в конце.
• Все анаграммы в строке: Окно несёт счётчики букв вместо суммы.
• Перестановка в строке: Те же счётчики, но останов на первом совпадении.
• Повторяющиеся последовательности ДНК: Каждое окно из десяти символов, подсчёт в словаре.
• Максимум скользящего окна: Фиксированное окно, чей ответ требует монотонной дек-очереди.
• Средние в радиусе k: Окно центрируется на индексе, а не тянется за ним.

Скользящее окно (фиксированный размер): сложность по времени и памяти

O(n)

n до 1e6 при окне размера k даёт O(n). Каждый элемент один раз входит в окно и один раз выходит.