Вибір патерна: швидкість, памʼять і читабельність

1. Навіщо обирати патерн замість двох вкладених циклів

Якщо ви новачок, бажання написати «просто два цикли» цілком нормальне. Це як узяти лопату й викопати котлован: працює, зрозуміло, мозок не перегрівається. Проблема починається тоді, коли «котлован» раптом розміром зі стадіон: програма формально правильна, але відповіді доводиться чекати довше, ніж вариться гречка. І це вже боляче.

Зафіксуймо просту річ: ми обираємо патерн не заради моди, а заради часу виконання й спокою. Вкладені цикли по масиву часто дають O(n²). Один прохід — O(n). Різниця звучить як «ну, удвічі», але насправді це «у тисячу разів і ще трохи зверху».

Щоб відчути це на практиці, можна зробити невелику оцінку «скільки операцій» — дуже грубо, зате корисно для інтуїції:

import Foundation

func roughOperationsQuadratic(n: Int) -> Int { n * n }
func roughOperationsLinear(n: Int) -> Int { n }

let n = 10_000
print("O(n)  ~= \\(roughOperationsLinear(n: n))")      // O(n) ≈ 10000
print("O(n²) ~= \\(roughOperationsQuadratic(n: n))")   // O(n²) ≈ 100000000

І ось тут зазвичай настає момент: «А можна без ста мільйонів?» Можна — якщо задача підходить до одного з патернів на сьогодні.

2. Як за умовою зрозуміти, чого від вас хочуть

Коли ви бачите задачу, важливо не одразу бігти в код, а на 20–30 секунд поставити собі запитання: що саме потрібно знайти — пару, вікно, найкращий відрізок чи багато запитів на діапазонах? Ця пауза потім економить пів години налагодження.

Нижче — компактна «карта вибору». Це не священна таблиця, але вона чудово допомагає, поки ви набиваєте руку.

Важливо: якщо ви читаєте задачу й у голові одразу зʼявляється «ну тут два цикли» — це не помилка. Це ваш базовий спосіб мислення пропонує гарантовано робоче рішення. Просто тепер у вас є другий шар мислення: «а чи немає тут вікна, відрізка, пар або запитів на діапазони?»

3. Швидкий детектор O(n²): червоні прапорці

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

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

Подивімося на класичний наївний приклад: усі суми вікон розміру k:

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
}

Цей код милий і зрозумілий, але в ньому чітко видно: для кожного start ми знову й знову перераховуємо майже одні й ті самі елементи. Саме такі повтори й є «паливом» для sliding window.

Другий червоний прапорець — повторювані запити до одного й того ж масиву, особливо «сума на діапазоні». Якщо у вас один запит — цикл нормальний. Якщо 1000 запитів — уже хочеться префікси.

Третій червоний прапорець — неочевидна вартість операцій. Іноді код виглядає «майже O(n)», але всередині ховається щось дороге. Навіть стандартні операції можуть несподівано стати O(n) залежно від типу колекції та того, як ви її отримали. У Swift, наприклад, бувають ситуації, коли обчислення count або отримання last може виявитися дорожчим, ніж ви інтуїтивно очікуєте, якщо ви працюєте не зі звичайним масивом, а з більш «хитрою» послідовністю або колекцією. Такі моменти обговорюються в матеріалах про колекції та вартість операцій, і це добрий приклад того, що складність іноді ховається в деталях API.

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

4. Вибір патерна: швидкість vs памʼять

Дуже легко потрапити в пастку «O(n) за будь-яку ціну». Але алгоритми — це завжди компроміс. Ми сьогодні обираємо між трьома ресурсами: часом, памʼяттю та зрозумілістю коду.

Prefix sums — ідеальний приклад. Вони дають швидкі запити O(1), але потребують додаткового масиву довжини n + 1. Це чесна угода: ми платимо памʼяттю, щоб не перераховувати суми заново.

Щоб це відчути, давайте зробимо крихітний приклад для нашого навчального файла ArrayPatternsDemo.swift. Уявіть, що ми пишемо консольну утиліту «аналітика за числами» — умовно про кроки за день, сторінки чи витрати; не має значення. Нам потрібно іноді швидко відповідати на запити «сума з дня l по день r».

Побудова префіксів:

import Foundation

func buildPrefixSums(_ numbers: [Int]) -> [Int] {
    var prefix = Array(repeating: 0, count: numbers.count + 1)
    for i in 0..<numbers.count {
        prefix[i + 1] = prefix[i] + numbers[i]
    }
    return prefix
}

Запит суми на включному діапазоні [l, r]:

import Foundation

func rangeSum(prefix: [Int], l: Int, r: Int) -> Int? {
    guard l >= 0, r >= l, (r + 1) < prefix.count else { return nil }
    return prefix[r + 1] - prefix[l]
}

І тут усе просто: якщо запитів мало — можна без префіксів. Якщо багато — префікси окуповуються.

5. Читабельність: коли швидше означає складніше

Дуже хочеться сказати «завжди робіть O(n)». Але давайте чесно: іноді O(n²) рішення простіше, а вхідні дані малі — і це нормально. Проблема починається тоді, коли ви не проговорили собі й читачеві коду, чому ви дозволили собі O(n²).

Професійна звичка тут проста: перед тим, як ускладнювати код патерном, оцініть ціну ускладнення.

Two pointers зазвичай читабельні, коли:

• є чітке правило руху,
• інваріант можна сформулювати одним реченням,
• умова завершення проста (left < right).

Prefix sums читабельні майже завжди, якщо ви строго дотримуєтеся домовленості щодо індексів: prefix[i] = сума numbers[0..<i].

Variable window стає нечитабельним, якщо ви не можете словами пояснити, чому left рухається саме так. Тоді код перетворюється на «магічне смикання індексів», і через тиждень ви самі собі не повірите, що це писали ви.

Гарний критерій читабельності: якщо ви не можете пояснити алгоритм уголос за 30 секунд, не торкаючись коду, — значить, ви поки не готові писати його “на автоматі”. Краще спростити або хоча б залишити собі зрозумілий коментар-інваріант.

6. Дерево рішень: як обрати патерн

Зараз зберемо все в один простий алгоритм вибору. Уявіть, що ви стоїте перед задачею, і у вас є 6 запитань. Це не список «для галочки», а коротка внутрішня діагностика.

flowchart TD
    A["Задача на масиві"] --> B{"Потрібна пара елементів?"}
    B -->|Так| C["Two pointers (якщо масив відсортований / є правило руху)"]
    B -->|Ні| D{"Працюємо з відрізками (неперервні індекси)?"}
    D -->|Ні| E["Не наш випадок: можливо, потрібна інша структура (але сьогодні не заглиблюємося в Dictionary/Set)"]
    D -->|Так| F{"Потрібні значення для всіх вікон розміру k?"}
    F -->|Так| G["Fixed sliding window: running sum/агрегат"]
    F -->|Ні| H{"Потрібен найкращий/мінімальний відрізок під обмеження?"}
    H -->|Так| I["Variable sliding window (якщо умова \"піддається\" зсуву left)"]
    H -->|Ні| J{"Багато запитів суми по діапазонах?"}
    J -->|Так| K["Prefix sums: build O(n) + query O(1)"]
    J -->|Ні| L["Можливо, достатньо простого циклу O(n) або навіть O(n²) за малого n"]

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

7. Контракт функції та точка оновлення відповіді

У новачків часто «зависає» не алгоритм, а домовленість щодо результату. Наприклад: «якщо пару не знайшли — повернути 0?» А якщо 0 — це валідний індекс? А якщо масив порожній? Оце все — не дрібниці, це фундамент.

На цьому етапі ми вже вміємо повертати Optional, і це найкращий спосіб чесно сказати: «відповідь може бути відсутня».

Контракт: що повертаємо, якщо відповіді немає

Приклад: функція пошуку пари індексів у відсортованому масиві. Зверніть увагу, як сигнатура заздалегідь фіксує контракт: ми повертаємо саме індекси, і саме nil, якщо не знайшли.

import Foundation

func twoSumSorted(_ numbers: [Int], target: Int) -> (Int, Int)? {
    guard numbers.count >= 2 else { return nil }

    var left = 0
    var right = numbers.count - 1

    while left < right {
        let sum = numbers[left] + numbers[right]
        if sum == target { return (left, right) }
        sum < target ? (left += 1) : (right -= 1)
    }
    return nil
}

І тепер код, що викликає цю функцію, теж стає чистішим: ви не плутаєте «0 як відповідь» і «0 як ознаку помилки».

Точка оновлення відповіді: де саме ви “фіксуєте найкращий варіант”

Є одна річ, яка псує настрій частіше, ніж Index out of range: ви оновили відповідь не в той момент.

Наприклад, у variable sliding window для задачі «мінімальна довжина відрізка із сумою ≥ target» правильна логіка така: щойно умова виконується (sum >= target), вікно вже валідне, і ви можете покращити відповідь. А потім починаєте звужувати вікно, щоб зробити його ще коротшим.

import Foundation

func minLenAtLeast(_ target: Int, numbers: [Int]) -> Int? {
    guard target > 0 else { return nil }

    var left = 0
    var sum = 0
    var best: Int? = nil

    for right in 0..<numbers.count {
        sum += numbers[right]

        while sum >= target {
            let len = right - left + 1
            best = best.map { min($0, len) } ?? len

            sum -= numbers[left]
            left += 1
        }
    }
    return best
}

Якщо ви випадково переставите рядки й оновите best після left += 1, ви почнете втрачати кандидатів. Код компілюватиметься, іноді навіть працюватиме, але на підступному тесті дасть хибний результат.

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

8. Мініпроєкт: один масив і різні запити

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

Запитання: чи є два дні, які дають рівно target

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

import Foundation

let sortedDaily = [1, 3, 4, 7, 10, 12]
if let (i, j) = twoSumSorted(sortedDaily, target: 14) {
    print("Знайшли пару: \\(sortedDaily[i]) + \\(sortedDaily[j])") // Знайшли пару: 4 + 10
} else {
    print("Пари немає")
}

Якщо масив не відсортований, two pointers «з кінців» не працює так красиво — і це добрий приклад межі застосовності патерна.

Запитання: максимальна сума за будь-які k днів поспіль

Це типова задача на «усі вікна однакової довжини».

import Foundation

func maxSumWindow(_ 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
}

Запитання: мінімальна кількість днів поспіль, щоб набрати щонайменше target

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

import Foundation

let daily = [2, 3, 1, 2, 4, 3] // усі невідʼємні
print(minLenAtLeast(7, numbers: daily) ?? -1) // 2 (відрізок [4,3])

Запитання: у мене 500 запитів «сума з дня l по день r»

Prefix sums окуповуються саме великою кількістю запитів.

import Foundation

let prefix = buildPrefixSums(daily)
print(rangeSum(prefix: prefix, l: 1, r: 3) ?? -1) // 6 (3+1+2)
print(rangeSum(prefix: prefix, l: 0, r: 5) ?? -1) // 15

І в цей момент стає видно, навіщо взагалі потрібна лекція про вибір патерна: один і той самий масив, але різні запити, і «найкращий» підхід щоразу інший.

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

Помилка №1: «патерн про всяк випадок», без причини.
Іноді студент вивчив prefix sums і починає будувати префікси всюди, навіть якщо потрібен один запит. Проблема не в тому, що це «погано», а в тому, що ви платите складністю коду й памʼяттю за вигоду, якою не користуєтеся. Це як купити вантажівку заради одного пакета молока: доїдете, але навіщо.

Помилка №2: змішування домовленостей щодо діапазонів [l, r] і [l, r) в одному рішенні.
У префіксів і вікон є непорушне правило — домовленість про індекси. Якщо ви сьогодні рахуєте суму для включного [l, r] через prefix[r + 1] - prefix[l], а завтра в сусідній функції раптом використовуєте логіку half-open [l, r), ви отримаєте «правильний код із неправильною відповіддю». Це особливо підступно, тому що компілятор вам не допоможе — усе легально.

Помилка №3: variable window без передумов (особливо за відʼємних чисел).
Змінне вікно працює, коли умова «піддається» руху left уперед без відкатів. Для сум це зазвичай означає невідʼємні елементи. Якщо в масиві є відʼємні числа, сума може зменшуватися під час розширення вікна, і алгоритм перестає бути коректним. Помилка виглядає як «ну я ж рухаю left і right, чому не працює?» — тому що інваріант відсутній.

Помилка №4: забули посунути вказівник в одній із гілок — нескінченний цикл.
Two pointers і variable window вимагають залізного правила: на кожній ітерації хтось має зсунутися. Якщо ви написали while left < right, але в гілці else не змінюєте ні left, ні right, цикл стає вічним. Це той випадок, коли програма не падає, не свариться, а просто «думає про вічне» й нічого не виводить.

Помилка №5: неправильна точка оновлення відповіді.
У fixed window зазвичай усе просто: оновили суму — оновили й відповідь. У variable window часто потрібно оновлювати відповідь до зсуву left, інакше ви втрачаєте найкращого кандидата. Ця помилка особливо неприємна тим, що на маленьких прикладах може «випадково проходити», а на справжніх даних ламає результат.