Ковзне вікно фіксованого розміру

1. Ковзне вікно фіксованого розміру: ідея та мотивація

Коли в задачі трапляється щось на кшталт «для кожного відрізка довжини k порахуй суму, середнє або максимум», у новачка часто вмикається внутрішній калькулятор: «Ну, я ж можу взяти перші k, додати їх, потім посунутися на 1 і ще раз усе порахувати…». Формально це працює, але з часом код починає гальмувати. Саме тут і стає в пригоді патерн sliding window фіксованого розміру: вікно довжини k «їде» по масиву, а ми оновлюємо відповідь за O(1) на кожному кроці.

Що таке «вікно»

Вікно — це неперервний шматок масиву, тобто відрізок за індексами. Фіксоване вікно означає, що довжина цього відрізка завжди однакова і дорівнює k. Наприклад, за k = 3 ми розглядаємо вікна [0...2], потім [1...3], потім [2...4] і так далі — доки вікно ще вміщується в масиві.

Ось зручна візуалізація для масиву numbers:

numbers:  [ 5, 2, 7, 1, 3, 6 ]
k = 3

вікно #1:  [ 5, 2, 7 ]  -> indices 0...2
вікно #2:     [ 2, 7, 1 ] -> indices 1...3
вікно #3:        [ 7, 1, 3 ] -> indices 2...4
вікно #4:           [ 1, 3, 6 ] -> indices 3...5

Наївний підхід і чому він O(n·k)

Перш ніж щось оптимізувати, важливо зрозуміти, де саме вузьке місце. Наївне рішення звучить логічно: «Пройдуся по всіх можливих стартах вікна, а потім усередині ще раз пройдуся по k елементах і порахую суму». І ось у вас з’являються два цикли: зовнішній за стартом вікна, внутрішній за елементами вікна.

Скільки операцій тут виходить? Приблизно (n - k + 1) вікно, і кожне з них ви рахуєте за k кроків. Отже, маємо (n - k + 1) * k, а це по суті — O(n·k). Якщо k велике, це вже майже O(n²).

Покажу короткий код наївного рішення, щоб потім було з чим порівняти оптимальний варіант:

import Foundation

func windowSumsNaive(_ numbers: [Int], k: Int) -> [Int] {
    guard k > 0, numbers.count >= k else { return [] }

    var result: [Int] = []
    for start in 0...(numbers.count - k) {
        var sum = 0
        for i in start..<(start + k) {
            sum += numbers[i]
        }
        result.append(sum)
    }
    return result
}

Цей код коректний, але в ньому є сигнал тривоги: внутрішній цикл щоразу заново перераховує майже ті самі елементи. Нам потрібно навчитися не перераховувати те, що вже порахували.

2. Running sum: «входить один, виходить один»

Тепер оптимізуємо по-людськи. Уявіть, що у вас є вікно довжини k, і ви знаєте його суму. Коли вікно зсувається на один елемент праворуч, стаються рівно дві речі: один елемент виходить із вікна — найлівіший, а один елемент входить — новий праворуч. Отже, нова сума — це стара сума плюс «той, що входить», мінус «той, що виходить». Усе.

Цю суму, яку ми підтримуємо на ходу, зазвичай називають running sum — сумою «на ходу». Формула під час зсуву на 1:

sum = sum + numbers[i] - numbers[i - k]

Де i — індекс нового елемента, що входить, тобто права межа вікна. Якщо розмір вікна дорівнює k, то елемент, який виходить, розташований рівно на k позицій лівіше: i - k.

Щоб не заплутатися, корисно один раз зафіксувати таблицю відповідностей:

k

sum

i

i - k

І важливий практичний висновок: у вікні фіксованого розміру майже завжди два етапи — спочатку ми ініціалізуємо суму першого вікна, а потім проходимо по масиву, оновлюючи суму за O(1).

Канонічна схема fixed window

Щоб патерн запам’ятався як рефлекс — у хорошому сенсі —, корисно тримати в голові одну й ту саму структуру коду. Вона трапляється знову і знову: максимум суми, середнє, кількість вікон з умовою — усе це одна й та сама «рама», тільки «картина всередині» різна.

Ось схема думок, майже як блок-схема:

flowchart TD
    A["Перевірте контракт: k > 0 і n >= k"] --> B["Обчисліть суму першого вікна 0..<k"]
    B --> C["best = sum (або збережіть результат першого вікна)"]
    C --> D["for i in k..<n: зсуваємо вікно"]
    D --> E["sum += numbers[i]"]
    E --> F["sum -= numbers[i - k]"]
    F --> G["Оновіть відповідь: max/min/append/count..."]
    G --> D

Якщо ви впізнаєте цю схему в задачі — вітаю: ви бачите патерн, а не просто код.

Маленьке, але важливе застереження: тут ми говоримо про Array, де доступ за індексом зазвичай вважається O(1). У ширшому світі Swift вартість індексних операцій залежить від того, чи є колекція RandomAccessCollection; для масивів — так, для деяких інших колекцій — є нюанси.

3. Приклади задач на fixed window

Максимальна сума серед усіх вікон довжини k

Тепер візьмемо найкласичніший приклад: знайти максимальну суму серед усіх вікон довжини k. Зверніть увагу на контракт. Якщо k <= 0 або масив коротший за k, вікон немає — отже, чесно повертаємо nil.

import Foundation

func maxWindowSum(_ numbers: [Int], k: Int) -> Int? {
    guard k > 0, numbers.count >= k else { return nil }

    var sum = 0
    for i in 0..<k { sum += numbers[i] }

    var best = sum

    for i in k..<numbers.count {
        sum += numbers[i]
        sum -= numbers[i - k]
        best = max(best, sum)
    }

    return best
}

Перший цикл for ініціалізує суму першого вікна. Другий — зсуває вікно.

Щоб переконатися, що все справді працює, додамо мініперевірку в код верхнього рівня. У навчальних завданнях це цілком нормально:

import Foundation

let data = [5, 2, 7, 1, 3, 6]
if let best = maxWindowSum(data, k: 3) {
    print(best) // 14  (це вікно [5, 2, 7])
} else {
    print("Вікно не існує")
}

Ковзне середнє: обережно з Int і Double

Тепер зробимо те саме, але із середнім. Важливо: якщо ви зберігаєте суму як Int, а потім ділите sum / k, ви отримаєте цілочисельне ділення і втратите дробову частину. Тому результат краще повертати як Double.

Ключова ідея проста: суму оновлюємо як Int, а середнє обчислюємо в момент запису результату.

import Foundation

func movingAverages(_ numbers: [Int], k: Int) -> [Double] {
    guard k > 0, numbers.count >= k else { return [] }

    var result: [Double] = []

    var sum = 0
    for i in 0..<k { sum += numbers[i] }
    result.append(Double(sum) / Double(k))

    for i in k..<numbers.count {
        sum += numbers[i]
        sum -= numbers[i - k]
        result.append(Double(sum) / Double(k))
    }

    return result
}

Перевіримо на простому масиві, де легко відстежити арифметику:

import Foundation

let data = [10, 20, 30, 40]
let avgs = movingAverages(data, k: 2)
print(avgs) // [15.0, 25.0, 35.0]

Зверніть увагу: у масиві з 4 елементів є рівно 3 вікна довжини 2, отже й середніх теж три.

Рахуємо вікна, які задовольняють умову

На цьому етапі зазвичай стається корисний зсув у мисленні: ви починаєте розуміти, що fixed window — це не «задача про суму», а «задача про перебір вікон без перерахунку». Тому наступний приклад: порахувати, скільки вікон мають суму щонайменше limit.

Це зручно, бо ви бачите той самий running sum, але замість best у вас просто лічильник.

import Foundation

func countWindowsSumAtLeast(_ numbers: [Int], k: Int, limit: Int) -> Int {
    guard k > 0, numbers.count >= k else { return 0 }

    var sum = 0
    for i in 0..<k { sum += numbers[i] }

    var count = (sum >= limit) ? 1 : 0

    for i in k..<numbers.count {
        sum += numbers[i]
        sum -= numbers[i - k]
        if sum >= limit { count += 1 }
    }

    return count
}

Мініприклад:

import Foundation

let data = [1, 2, 3, 4, 5]
print(countWindowsSumAtLeast(data, k: 2, limit: 7)) // 2  (вікна [3,4] і [4,5])

4. Вбудовуємо в міні-застосунок LibraryStats

Щоб приклади не виглядали набором розрізнених функцій «у вакуумі», давайте уявимо наш невеликий консольний проєкт, який ми поступово розвиваємо: LibraryStats. Він поки не керує книгами й не зберігає дані у файлах, але вже вміє аналізувати числові ряди — наприклад, «скільки видач книг було за днями».

Сценарій простий: користувач вводить числа через пробіл — це видачі за днями. Потім вводить k — розмір вікна. Ми виводимо максимальну суму за k днів поспіль і список середніх.

Почнемо з утиліти читання масиву чисел. Тут важливо не ускладнювати: split, compactMap — і готово.

import Foundation

func readInts() -> [Int] {
    let line = readLine() ?? ""
    return line.split(separator: " ").compactMap { Int($0) }
}

Тепер код верхнього рівня, який використовує вже написані функції:

import Foundation

print("Введіть видачі за днями (через пробіл):", terminator: " ")
let daily = readInts()

print("Введіть розмір вікна k:", terminator: " ")
let k = Int(readLine() ?? "") ?? 0

if let best = maxWindowSum(daily, k: k) {
    print("Максимум видач за \(k) днів поспіль: \(best)")
} else {
    print("Вікно розміру \(k) не існує для масиву довжини \(daily.count)")
}

let avgs = movingAverages(daily, k: k)
print("Ковзне середнє:", avgs) // наприклад: [12.3, 11.7, ...]

Так, це поки що дуже навчальний приклад. Але це чесний розвиток: ми вчимося будувати обчислення навколо масивів, тримати контракти (nil/[]) і не перераховувати одне й те саме по сто разів.

5. Індекси та складність

Дисципліна індексів

У sliding window фіксованого розміру головна складність — не математика. Вона справді проста. Головна складність — межі індексів. Тому зафіксуємо два критичні факти.

Перший факт: другий цикл починається з i = k, бо індекс k — це перший «новий елемент, що входить», який ще не був у першому вікні.

Другий факт: індекс елемента, що виходить, — це i - k.

Іноді допомагає мікротаблиця для конкретних чисел. Нехай k = 3. Тоді:

i

3

numbers[3]

numbers[0]

4

numbers[4]

numbers[1]

5

numbers[5]

numbers[2]

Коли це один раз стає зрозумілим, далі fixed window працює майже на автоматі.

Складність і памʼять

Один раз рахуємо суму перших k елементів — це O(k). Потім проходимо решту n - k елементів, і на кожному кроці виконуємо сталу кількість операцій — це O(n).

За памʼяттю все зазвичай доволі скромно. Якщо вам потрібне лише одне число, наприклад максимальна сума, то додаткова пам’ять O(1): кілька змінних. Якщо ж ви хочете повернути масив усіх середніх або сум, то пам’ять уже O(n), бо ви зберігаєте результати, — але це чесна пам’ять під відповідь.

6. Типові помилки

Помилка №1: забули відняти елемент, що виходить.
Це трапляється найчастіше. У підсумку сума росте, мов снігова куля. Добре допомагає простий підхід: сприймайте зсув вікна як пару операцій, що завжди йдуть разом — + вхідний і - вихідний.

Помилка №2: другий цикл стартує не з k, а з k - 1 або k + 1.
Коли старт неправильний, формула i - k або дає від’ємний індекс, або ви пропускаєте одне вікно й отримуєте «майже правильну» відповідь. Виправляється це так: зафіксуйте зміст i. Це індекс елемента, що входить, а перший елемент, що входить після першого вікна, має індекс рівно k.

Помилка №3: переплутали кількість вікон і межі стартів.
Масив довжини n містить рівно n - k + 1 вікон довжини k (якщо n >= k). У running sum зазвичай зручніше мислити «вхідним індексом» i з діапазону k..<n.

Помилка №4: середнє обчислюється як Int і втрачає дробову частину.
У Swift вираз sum / k за Int дає Int. Тому в moving average краще ділити як Double(sum) / Double(k).

Помилка №5: немає перевірки контракту k > 0 і n >= k.
Іноді хочеться «зробити швидше», а потім раптом виявляється, що масив порожній, або k дорівнює 0, або користувач увів k більше за довжину масиву. Тому guard на початку — не бюрократія, а спосіб зробити поведінку передбачуваною.