1. Переменное окно: идея и отличие от fixed window
Если fixed window — это как вагон метро строго на 8 пассажиров (ни больше ни меньше), то variable window — это маршрутка: пока не переполнена — подбираем людей, переполнилась — кого-то высаживаем. В задачах на массивы это обычно выглядит так: мы хотим найти лучший отрезок (подмассив) по условию, но длина отрезка заранее неизвестна. Если вы чувствуете желание написать вложенные циклы «все старты × все концы», скорее всего, тут и появляется sliding window переменного размера.
Переменное окно почти всегда использует два индекса:
- right — расширяет окно вправо (мы как бы добавляем новый элемент в текущий отрезок),
- left — сужает окно слева, когда условие нарушается или когда мы хотим улучшить ответ.
Самое важное отличие от fixed window: длина окна не фиксирована, и второй указатель (left) может двигаться несколько раз на один шаг right. Но при этом общий прогон всё равно остаётся O(n), потому что left никогда не откатывается назад (а значит, двигается максимум n раз).
2. Инвариант и базовый шаблон
Перед тем как писать код, нужно на секунду остановиться и договориться с собой о двух вещах: что такое «окно» и что мы считаем «правильным окном». Это звучит почти философски, но на практике экономит часы отладки и спасает от off-by-one.
Мы будем считать, что окно — это включающий отрезок по индексам [left, right], то есть оба края входят в окно.
Теперь про инвариант. Инвариант — это утверждение, которое остаётся истинным на каждом шаге алгоритма. Для variable window чаще всего инвариант звучит так: «после того как мы сдвинули left, окно снова удовлетворяет условию (или максимально сжато, но всё ещё удовлетворяет)».
Небольшая визуализация окна:
numbers: [ 2, 3, 1, 2, 4, 3 ]
^ ^
left right
окно = numbers[left...right] // включительно
длина = right - left + 1
В этой лекции мы будем работать с ограничениями, которые легко поддерживать «на лету»: суммой или количеством “плохих” элементов. Мы сознательно не лезем в случаи, где нужно хранить частоты разных значений (это уже другая тема и другие структуры).
Ниже — «скелет», который полезно держать в голове: мы идём right слева направо, обновляем агрегат, а потом в цикле while двигаем left, пока окно не станет «валидным».
Каркас (псевдо-Swift, но очень близко к реальности):
var left = 0
var state = 0 // сумма / счётчик / что угодно
for right in 0..<numbers.count {
state = state + numbers[right] // расширяем окно вправо
while окно_невалидно(state) {
state = state - numbers[left] // убираем левый элемент
left += 1
}
// здесь окно валидно — можно обновлять ответ
}
Ключевой момент: внутри while вы обязаны реально двигать left. Если забыть сдвиг или забыть обновить state, получится «вечный цикл».
3. Ограничения и сложность
Почему для задач на сумму часто нужны неотрицательные числа
Variable window для сумм (типа «найти минимальный отрезок, где сумма >= target») обычно предполагает, что элементы неотрицательные.
Почему? Если элементы неотрицательные, то при расширении окна вправо сумма не уменьшается, а при сужении слева сумма не увеличивается. То есть сумма ведёт себя монотонно относительно действий указателей, и мы можем «чинить окно» без отката назад.
Если же в массиве есть отрицательные числа, вы можете сдвинуть right, сумма упадёт, потом сдвинуть left, сумма вырастет — и логика починки перестаёт быть корректной.
В этой лекции мы будем честными: там, где нужно допущение «все числа >= 0», мы будем проговаривать это прямо в тексте и в комментарии к функции.
Почему это O(n), даже если внутри есть while
Психологически это часто ломает новичков: «Но там же for, а внутри while… это же почти два цикла!» Здесь важно помнить: два цикла — не всегда O(n²). Важно не количество циклов, а сколько раз реально двигаются индексы.
right двигается ровно n раз (от 0 до n-1). А left тоже двигается максимум n раз, потому что он никогда не уменьшается. Значит, суммарно — не больше 2n, то есть O(n).
Небольшая блок-схема (идея соответствует коду):
flowchart TD
A[Start: left=0, state=0] --> B{right < n?}
B -- no --> Z[Finish]
B -- yes --> C["Add numbers[right] to state"]
C --> D{Window invalid?}
D -- no --> E["Update answer using (left,right)"]
E --> F[right += 1]
F --> B
D -- yes --> G["Remove numbers[left] from state"]
G --> H[left += 1]
H --> D
Если вы видите, что какой-то индекс может бегать туда-сюда, тогда да — сложность может стать хуже. Но в sliding window переменного размера принципиально важно: индексы только растут.
4. Примеры задач
Минимальная длина подмассива с суммой не меньше target
Это очень классическая задача, и она идеально показывает, зачем нужен while и почему важно обновлять ответ в правильный момент. Мы хотим найти самый короткий отрезок, сумма которого >= target. Если такого отрезка нет — вернём nil, потому что «отсутствие ответа» тут нормальная часть модели.
Мы будем расширять окно вправо, накапливая сумму. Как только сумма стала >= target, мы нашли какой-то подходящий отрезок, но он, скорее всего, не минимальный. Поэтому мы начинаем сжимать окно слева: пока сумма всё ещё >= target, мы пытаемся выкинуть лишнее и уменьшить длину.
import Foundation
/// Важно: корректно работает, если numbers содержит неотрицательные числа.
func minLengthSubarraySum(atLeast target: Int, in 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 length = right - left + 1
best = (best == nil) ? length : min(best!, length)
sum -= numbers[left] // убираем левый элемент
left += 1
}
}
return best
}
Обратите внимание на «точку обновления ответа»: мы считаем длину до того, как двинем left. Если сделать наоборот, вы буквально сотрёте из истории самое короткое окно, которое только что было валидным.
Возьмём numbers = [2, 3, 1, 2, 4, 3], target = 7. В какой-то момент окно будет [1, 2, 4] (сумма 7, длина 3), а потом даже [4, 3] (сумма 7, длина 2).
Чтобы совсем не потеряться, удобно держать маленькую табличку в голове:
| Действие | Что двигаем | Что происходит с суммой |
|---|---|---|
| Расширяем окно | |
|
| Сужаем окно | |
|
Это простая таблица, но она реально спасает от ошибки «вычел не то».
Максимальная длина подмассива с суммой не больше limit
Теперь зеркальная задача: хотим самый длинный отрезок, сумма которого <= limit. Здесь логика тоже на variable window, но точка обновления ответа обычно стоит после того, как мы «починили окно». Потому что нас интересуют только валидные окна.
import Foundation
/// Важно: корректно работает, если numbers содержит неотрицательные числа.
func maxLengthSubarraySum(atMost limit: Int, in numbers: [Int]) -> Int {
guard limit >= 0 else { return 0 }
var left = 0
var sum = 0
var best = 0
for right in 0..<numbers.count {
sum += numbers[right] // расширяем
while sum > limit && left <= right { // чиним окно
sum -= numbers[left]
left += 1
}
// теперь sum <= limit, окно валидно
best = max(best, right - left + 1)
}
return best
}
Обратите внимание на left <= right в условии while. Формально в корректных данных можно и без него, но для новичка это хороший «предохранитель», чтобы не уйти в отрицательную длину окна, если вход странный.
Максимальная длина: в окне не больше K нулей
Суммы — не единственная жизнь variable window. Иногда условие — это не сумма, а «сколько плохих элементов мы позволяем в окне». Например: дан массив из 0 и 1. Хотим найти максимальную длину отрезка, где нулей не больше k.
Идём right слева направо. Если зашёл ноль — увеличили zeroCount. Если zeroCount стал больше k, окно «сломалось», и мы двигаем left, пока нулей снова не станет допустимо.
import Foundation
func maxLengthWithAtMostKZeros(_ bits: [Int], k: Int) -> Int {
guard k >= 0 else { return 0 }
var left = 0
var zeroCount = 0
var best = 0
for right in 0..<bits.count {
if bits[right] == 0 { zeroCount += 1 }
while zeroCount > k {
if bits[left] == 0 { zeroCount -= 1 }
left += 1
}
best = max(best, right - left + 1)
}
return best
}
Здесь нет сумм, нет арифметики, но паттерн тот же самый: right расширяет, left чинит, инвариант говорит «после while окно валидно».
5. Встраиваем в учебное консольное приложение
Чтобы не превращать лекцию в набор отдельных функций «где-то в тетрадке», продолжим маленькое учебное приложение. Представим, что у нас есть файл main.swift, и мы запускаем его в IDE или Web-IDE. Программа читает одну команду и массив, а затем печатает результат.
Формат ввода сделаем простым: одна строка. Например:
- minlen 7 2 3 1 2 4 3
- maxlen 7 2 3 1 2 4 3
- zeros 1 1 1 0 1 0 1 1
Где первое слово — команда, второе (иногда) — параметр (target, limit, k), остальное — числа массива.
Парсинг строки в токены
import Foundation
func readTokens() -> [String] {
let line = readLine() ?? ""
return line.split(separator: " ").map(String.init)
}
Ничего сложного, но важный принцип: мы не пытаемся «умно угадывать» формат, мы просто честно разбиваем строку по пробелам.
Преобразование токенов в числа
import Foundation
func parseInts(_ tokens: ArraySlice<String>) -> [Int] {
tokens.compactMap { Int($0) }
}
compactMap пропускает то, что не превратилось в Int. На учебных задачах это нормально: мы считаем, что ввод более-менее корректный. Если вам хочется строже — можно сделать через guard, но сегодня наша цель не «идеальный парсер», а паттерн окна.
Склейка: выбираем алгоритм по команде
import Foundation
let tokens = readTokens()
guard tokens.count >= 3 else {
print("Usage: minlen target numbers... | maxlen limit numbers... | zeros k bits...")
exit(0)
}
let command = tokens[0]
let value = Int(tokens[1]) ?? 0
let numbers = parseInts(tokens.dropFirst(2))
switch command {
case "minlen":
let ans = minLengthSubarraySum(atLeast: value, in: numbers)
print(ans ?? -1) // -1 = "не найдено"
case "maxlen":
let ans = maxLengthSubarraySum(atMost: value, in: numbers)
print(ans)
case "zeros":
let ans = maxLengthWithAtMostKZeros(numbers, k: value)
print(ans)
default:
print("Unknown command: \(command)")
}
Здесь -1 для minlen — чисто UX-решение для консоли: так проще увидеть отсутствие ответа. Внутри алгоритма мы всё равно возвращаем Int?, то есть выражаем модель «может не найтись» корректно.
6. Как понять, что variable window вам подходит
Иногда самая сложная часть — не написать код, а вообще догадаться, что это sliding window переменного размера. Хорошая «проверка на здравый смысл» звучит так: после расширения окна вправо вы должны уметь восстановить валидность окна, двигая только левую границу, и при этом не нуждаться в откате назад.
Для сумм это обычно означает, что данные неотрицательные и условие сформулировано так, что при сдвиге left окно становится «не хуже» в смысле нарушения ограничения. Для счётчиков типа «не больше k плохих элементов» это означает, что вы можете поддерживать количество плохих элементов за O(1) на каждом шаге.
Если же ваше условие зависит от «самого частого элемента» или «количества разных значений», то вы уже интуитивно чувствуете: «кажется, мне нужна какая-то память о содержимом окна». Но сегодня мы туда не идём — держим фокус на чистом массиве и простом агрегате.
7. Типичные ошибки
Ошибка №1: использовать if вместо while при сужении окна.
Когда окно невалидно, его часто нужно сжать не на один шаг, а на много шагов подряд. Если вы сделаете «один сдвиг», окно может остаться невалидным, а вы пойдёте дальше и начнёте обновлять ответ на «сломанных» данных. Правильная мысль такая: «чиню окно до конца», поэтому почти всегда нужен while.
Ошибка №2: обновлять ответ в неправильный момент.
В задаче на минимальную длину при условии sum >= target вы обязаны обновить ответ до того, как вычтете numbers[left] и сдвинете left. В задаче на максимальную длину наоборот: вы обновляете ответ после починки, потому что вам нужны только валидные окна.
Ошибка №3: забыть проговорить (или проверить) предпосылки про данные.
Если вы решаете задачу «сумма на отрезке» sliding window’ом и молча допускаете отрицательные числа, алгоритм может начать возвращать неверные ответы без единой ошибки компиляции. Поэтому прямо в комментарии к функции полезно написать: «работает для неотрицательных чисел».
Ошибка №4: потерять дисциплину индексов и длины окна.
Длина включающего окна — это right - left + 1. Если забыть + 1, ответы будут стабильно на 1 меньше.
Ошибка №5: допустить «вечный цикл» внутри while.
Внутри while обязательно должно происходить изменение состояния, которое приближает вас к выходу из цикла: обычно это сдвиг left и корректное обновление агрегата (sum, zeroCount и т.д.). Если вы двигаете left, но забываете обновить агрегат, условие может оставаться истинным навсегда — и программа зависнет.
ПЕРЕЙДИТЕ В ПОЛНУЮ ВЕРСИЮ