Суммы окон фиксированного размера
Сдвигайте окно длины k за O(n)
«Суммы окон фиксированного размера» — бесплатный урок Coding Interview Prep на CoddyKit. Это урок 1 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Coding Interview Prep, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Coding Interview Prep содержит 4 уроков всего.
Задача о повторном суммировании
Во многих задачах требуется найти сумму каждого блока из k последовательных элементов. Пересчитывать сумму каждого блока с нуля неэффективно — это можно сделать лучше. 🪟
Сначала медленный способ
Наивная идея заключается в том, чтобы отдельно складывать элементы каждого окна длины k. Это приводит к повторным вычислениям и сложности O(n умножить на k), что слишком медленно для больших входных данных.
for i in range(n - k + 1):
s = sum(a[i:i + k])Главная идея
Соседние окна почти полностью перекрываются. При перемещении на один шаг вправо нужно только удалить самый левый элемент и добавить новый элемент справа.
Задайте первое окно
Сначала один раз просуммируйте первые k элементов. Эта сумма станет основой, которую Вы будете обновлять при каждом дальнейшем сдвиге окна.
window = sum(a[:k])
best = windowСдвиньте на один шаг
Чтобы переместить окно, добавьте входящий элемент и вычтите выходящий. Благодаря этому каждый шаг требует постоянного объёма работы O(1).
for i in range(k, n):
window += a[i] - a[i - k]Отслеживайте ответ
После каждого сдвига обновляйте нужное значение, например максимальную сумму окна, найденную к этому моменту. Значение для текущего окна всегда доступно мгновенно.
best = max(best, window)Общая сложность линейна
Вы обращаетесь к каждому элементу один раз, чтобы добавить его, и ещё один раз, чтобы удалить, поэтому весь проход имеет сложность O(n). Этого достаточно даже при больших ограничениях.
Следите за индексами
Элемент, выходящий из окна, имеет индекс a[i - k], а не a[i - 1]. Неправильное смещение — самая распространённая ошибка в задачах с окном фиксированной длины.
Среднее получается бесплатно
Нужно найти не сумму, а максимальное среднее окна? Просто разделите отслеживаемую сумму окна на k. Логика скользящего окна совсем не изменится.
avg = window / kОбрабатывайте короткие массивы
Если массив короче k, полного окна не существует. Заранее сравните len(a) с k и сразу верните результат, чтобы избежать ошибки индекса.
if n < k:
return NoneКогда подходят окна фиксированной длины
Используйте этот шаблон, когда длина окна фиксирована, а значения можно объединять простым способом: например, находить сумму, количество или простые текущие статистики.
Быстрая проверка
Вы перемещаете окно размера k на один шаг вправо по массиву.
Итоги
Один раз задайте первое окно, а затем на каждом шаге добавляйте и вычитайте элементы, сдвигая окно за O(1). Весь проход по окну фиксированного размера выполняется за линейное время. ✅
Часто задаваемые вопросы
Урок «Суммы окон фиксированного размера» бесплатный?
Да — полный текст урока «Суммы окон фиксированного размера» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Coding Interview Prep, подпишись на CoddyKit PRO. Курс Coding Interview Prep содержит 4 уроков всего.
Чему я научусь в уроке «Суммы окон фиксированного размера»?
Сдвигайте окно длины k за O(n) Ты практикуешь Coding Interview Prep с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать Coding Interview Prep?
Предыдущий опыт не требуется. Coding Interview Prep на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 1 из 4.
Сколько времени занимает урок «Суммы окон фиксированного размера»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке Coding Interview Prep?
Да. Каждый урок Coding Interview Prep включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.
Все уроки этого курса
- Суммы окон фиксированного размера
- Окно переменного размера с двумя указателями
- Самая длинная подстрока без повторов
- Подсчёт окон, удовлетворяющих правилу