2. Фиксированное и динамическое окно

«Если рамки задачи заданы строго — держите строй. Если границы гибки — позвольте им сжиматься и расширяться по законам монотонности».
— Дональд Кнут

Тема: Паттерны скользящего окна, каркасы алгоритмов, выбор стратегии сжатия
Ссылки: Теория: Скользящее окно, Maximum Average Subarray I, Longest Substring, Minimum Window Substring

1. Дерево выбора типа окна

При первом взгляде на задачу со скользящим окном Senior-инженер определяет категорию по двум ключевым признакам:

flowchart TD
    classDef process fill:#1e293b,stroke:#38bdf8,stroke-width:1px,color:#f8fafc
    classDef success fill:#064e3b,stroke:#34d399,stroke-width:1px,color:#f8fafc
    classDef error   fill:#7f1d1d,stroke:#f87171,stroke-width:1px,color:#f8fafc
    classDef warning fill:#78350f,stroke:#fbbf24,stroke-width:1px,color:#f8fafc
    classDef entry   fill:#1e3a5f,stroke:#38bdf8,stroke-width:2px,color:#f8fafc

    Start["Задача на непрерывный подмассив/подстроку"]:::entry --> Q1{"Длина окна K задана жестко<br>в условии задачи?"}:::warning

    Q1 -->|"Да (K константно)"| Fixed["1. Фиксированное окно<br>(Fixed-size Window)"]:::success
    Fixed --> F_Simple["Простая метрика: сумма, среднее<br>(сложение и вычитание)"]:::process
    Fixed --> F_Complex["Сложное состояние: анаграммы p<br>(частотный массив [26]int)"]:::process

    Q1 -->|"Нет (длина плавает)"| Variable["2. Динамическое окно<br>(Variable-size Window)"]:::success
    Variable --> V_Max["Ищем МАКСИМАЛЬНУЮ длину:<br>сжимаем только при нарушении"]:::process
    Variable --> V_Min["Ищем МИНИМАЛЬНУЮ длину:<br>сжимаем пока условие выполняется"]:::process
  

2. Тип 1: Фиксированное скользящее окно

Сигналы в условии:

• «Дан массив и целое число $K$...»
• «Найти максимальное среднее значение среди всех подмассивов длины $K$».
• «Проверить, содержит ли строка перестановку длины $|P|$».

Архитектура алгоритма:

1. Фаза инициализации: вычисляем состояние для самого первого окна [0 .. K-1].
2. Фаза скольжения: запускаем цикл от индекса $K$ до $N-1$:
   • Включаем новый элемент: state += nums[i].
   • Исключаем старый элемент, выпавший слева: state -= nums[i-k].
   • Обновляем глобальный оптимум.

Идиоматичный Go-каркас:

func fixedSlidingWindow(nums []int, k int) int {
    if len(nums) < k {
        return 0
    }

    // 1. Инициализация первого окна
    currentSum := 0
    for i := 0; i < k; i++ {
        currentSum += nums[i]
    }
    maxSum := currentSum

    // 2. Скольжение окна
    for i := k; i < len(nums); i++ {
        currentSum += nums[i] - nums[i-k] // + новый, - старый
        maxSum = max(maxSum, currentSum)
    }

    return maxSum
}

3. Тип 2: Динамическое скользящее окно

Сигналы в условии:

• «Найти длину самой длинной подстроки без повторяющихся символов».
• «Найти минимальную длину подмассива с суммой не менее $S$».
• «Найти кратчайшее окно, содержащее все символы шаблона $T$».

Архитектура алгоритма:

Окно расширяется правым указателем right, пока оно легально. Как только инвариант нарушается, левый указатель left подтягивается вправо, сжимая окно и восстанавливая валидность.

Каркас для поиска МАКСИМАЛЬНОЙ длины:

func dynamicWindowMax(s string) int {
    var freq [128]int
    left := 0
    maxLen := 0

    for right := 0; right < len(s); right++ {
        // Расширяем окно вправо
        freq[s[right]]++

        // Сжимаем окно слева, пока условие нарушено
        for freq[s[right]] > 1 { // например, обнаружен дубликат
            freq[s[left]]--
            left++
        }

        // Окно валидно — фиксируем максимальную длину
        maxLen = max(maxLen, right-left+1)
    }

    return maxLen
}

Каркас для поиска МИНИМАЛЬНОЙ длины:

func dynamicWindowMin(nums []int, target int) int {
    left := 0
    currentSum := 0
    minLen := len(nums) + 1

    for right := 0; right < len(nums); right++ {
        currentSum += nums[right]

        // Пока условие выполняется — пытаемся СЖАТЬ окно слева,
        // чтобы сделать его еще меньше!
        for currentSum >= target {
            minLen = min(minLen, right-left+1)
            currentSum -= nums[left]
            left++
        }
    }

    if minLen > len(nums) {
        return 0 // решение не найдено
    }
    return minLen
}

4. Гибридный тип: фиксированная длина со сложным состоянием

Иногда длина окна фиксирована ($K = len(pattern)$), но сравнение окон требует учета частот символов (например, Permutation in String или Find All Anagrams).

Вместо примитивной суммы мы ведем массив частот:

var targetFreq, windowFreq [26]int
// Инициализируем шаблоны
for i := 0; i < len(p); i++ {
    targetFreq[p[i]-'a']++
    windowFreq[s[i]-'a']++
}

// Скользим окном длины len(p)
for i := len(p); i < len(s); i++ {
    if windowFreq == targetFreq {
        // Найдена анаграмма!
    }
    windowFreq[s[i]-'a']++           // вошел символ справа
    windowFreq[s[i-len(p)]-'a']--   // вышел символ слева
}

В Go сравнение массивов фиксированного размера windowFreq == targetFreq выполняется мгновенно за один вызов memequal (208 байт сравниваются аппаратно через регистры AVX/SSE).

5. Сравнительная шпаргалка

6. Mechanical Sympathy: предотвращение ловушек

7. Итог

• Фиксированное окно — прямолинейный инструмент: одно сложение, одно вычитание на каждом шаге.
• Динамическое окно — эластичный инструмент: растягивается в поисках новых элементов и сжимается до предела, находя локальный оптимум.

Переходим к первой практической задаче кластера — расчету максимального среднего значения: 3. Maximum Average Subarray I.