Техника скользящего окна для задач на подстроки, подмассивы и последовательности.
Универсальная техника для задач на подстроки и подмассивы: окно «скользит» по данным, избегая пересчёта и обеспечивая сложность O(n)
Sliding Window — это оптимизационная техника для задач, где требуется найти подстроку/подмассив с определёнными свойствами. Вместо перебора всех подстрок за O(n²), окно скользит по данным за O(n).
Массив — упорядоченная коллекция элементов одного типа.
Подмассив — непрерывная часть массива (элементы идут подряд).
Подпоследовательность — элементы массива в том же порядке, но не обязательно непрерывные.
Подстрока — непрерывная часть строки.
Префикс — начало строки (подстрока, начинающаяся с первого символа).
Суффикс — конец строки (подстрока, заканчивающаяся последним символом).
Хэш-функция — функция, преобразующая входные данные в число (хэш).
Хэш-таблица — структура данных для быстрого поиска по ключу (в среднем O(1)).
Коллизия — ситуация, когда два разных ключа дают одинаковый хэш.
Палиндром — строка, читающаяся одинаково слева направо и справа налево.
Анаграмма — строка, полученная перестановкой символов другой строки.
Подпоследовательность (строки) — строка, полученная удалением нуля или более символов без изменения порядка остальных.
| Тип | Описание | Пример |
|---|---|---|
| Фиксированный размер | Окно всегда k элементов | Maximum Sum Subarray of Size K |
| Переменный размер | Окно расширяется/сжимается по условию | Longest Substring Without Repeating |
| Два окна | Одновременно два окна | Permutation in String |
def sliding_window_variable(s):
left = 0
result = 0
window_state = {} # или Counter, set, etc.
for right in range(len(s)):
# Расширяем окно: добавляем s[right]
window_state[s[right]] = window_state.get(s[right], 0) + 1
# Сжимаем окно, пока условие не выполнено
while not valid_window(window_state):
window_state[s[left]] -= 1
if window_state[s[left]] == 0:
del window_state[s[left]]
left += 1
# Окно валидно — обновляем результат
result = max(result, right - left + 1)
return resultright += 1): добавляем элемент в окноleft += 1): удаляем элементы слева, пока условие не выполнитсяdef sliding_window_fixed(arr, k):
window_sum = sum(arr[:k]) # Начальное окно
max_sum = window_sum
for i in range(k, len(arr)):
# Сдвигаем окно: убираем arr[i-k], добавляем arr[i]
window_sum = window_sum - arr[i - k] + arr[i]
max_sum = max(max_sum, window_sum)
return max_sumСсылка: — (аналог LeetCode задач)
Условие:
Дан массив целых чисел arr и целое число k. Найдите максимальную сумму непрерывного подмассива размера ровно k.
Примеры:
Ввод: arr = [2, 1, 5, 1, 3, 2], k = 3 Вывод: 9 Объяснение: Подмассив [5, 1, 3] имеет максимальную сумму 9
Ввод: arr = [2, 3, 4, 1, 5], k = 2 Вывод: 7 Объяснение: Подмассив [3, 4] имеет сумму 7
Ограничения:
💡 Подсказка: Вычислите сумму первого окна размера k. Затем на каждом шаге сдвигайте окно: вычитайте уходящий элемент и добавляйте новый. Обновляйте максимум.
Решение:
def maxSubarraySum(arr, k):
if len(arr) < k:
return -1
window_sum = sum(arr[:k])
max_sum = window_sum
for i in range(k, len(arr)):
window_sum = window_sum - arr[i - k] + arr[i]
max_sum = max(max_sum, window_sum)
return max_sumОбъяснение:
Сложность:
Условие:
Дана строка s. Найдите длину самой длинной подстроки, не содержащей повторяющихся символов.
Примеры:
Ввод: s = "abcabcbb" Вывод: 3 Объяснение: Подстрока "abc" имеет длину 3
Ввод: s = "bbbbb" Вывод: 1 Объяснение: Подстрока "b" имеет длину 1
Ввод: s = "pwwkew" Вывод: 3 Объяснение: Подстрока "wke" имеет длину 3
Ограничения:
💡 Подсказка: Используйте set для хранения символов текущего окна. Если s[right] уже в set — удаляйте символы слева, пока не исчезнет дубликат. Обновляйте максимум длины.
Решение:
def lengthOfLongestSubstring(s):
char_set = set()
left = 0
max_len = 0
for right in range(len(s)):
# Если символ уже в окне — сжимаем слева
while s[right] in char_set:
char_set.remove(s[left])
left += 1
# Добавляем текущий символ
char_set.add(s[right])
# Обновляем максимум
max_len = max(max_len, right - left + 1)
return max_lenОбъяснение:
char_set хранит символы текущего окнаs[right] уже в set — удаляем слева, пока не исчезнетs[right], обновляем максимум длиныПример:
s = "abcabcbb"
right=0: {a}, max=1
right=1: {a,b}, max=2
right=2: {a,b,c}, max=3
right=3: 'a' уже в set → удаляем 'a', {b,c}, добавляем 'a', {b,c,a}, max=3
Сложность:
Условие:
Даны две строки s и t. Найдите минимальную подстроку в s, которая содержит все символы из t (с учётом частоты каждого символа).
Если такой подстроки нет, верните пустую строку.
Гарантируется, что ответ уникален.
Примеры:
Ввод: s = "ADOBECODEBANC", t = "ABC" Вывод: "BANC" Объяснение: Минимальная подстрока, содержащая все символы "ABC"
Ввод: s = "a", t = "a" Вывод: "a"
Ввод: s = "a", t = "aa" Вывод: "" Объяснение: Нет подстроки, содержащей два символа 'a'
Ограничения:
💡 Подсказка: Используйте Counter для хранения частот символов в t. Расширяйте окно, пока не найдёте все символы. Затем сжимайте для минимизации. Отслеживайте количество найденных символов.
Решение:
from collections import Counter
def minWindow(s, t):
if not s or not t:
return ""
# Частоты символов в t
need = Counter(t)
need_count = len(t) # Сколько символов ещё нужно найти
have = Counter()
left = 0
result = (float('inf'), 0, 0) # (длина, left, right)
for right, char in enumerate(s):
# Добавляем символ в окно
have[char] += 1
# Если этот символ ещё нужен — уменьшаем счётчик
if need[char] > 0:
need_count -= 1
need[char] -= 1 # Может стать отрицательным (лишние символы)
# Когда все символы найдены — сжимаем окно
while need_count == 0:
# Обновляем результат
if right - left + 1 < result[0]:
result = (right - left + 1, left, right)
# Удаляем s[left] из окна
have[s[left]] -= 1
need[s[left]] += 1
# Если символ стал нужен — увеличиваем need_count
if need[s[left]] > 0:
need_count += 1
left += 1
return "" if result[0] == float('inf') else s[result[1]:result[2] + 1]Объяснение:
need хранит, сколько каждого символа нужно из tneed_count — общее количество ещё не найденных символовneed_count > 0need_count == 0 — все символы найдены, сжимаем для минимизацииneed[char] может быть отрицательным — это лишние символыСложность:
Условие:
Даны две строки s и p. Найдите все индексы начала анаграмм p в строке s.
Анаграмма — строка, полученная перестановкой букв другой строки (те же символы с теми же частотами).
Примеры:
Ввод: s = "cbaebabacd", p = "abc" Вывод: [0, 6] Объяснение: Подстроки, начинающиеся с индексов 0 ("cba") и 6 ("bac"), являются анаграммами "abc"
Ввод: s = "abab", p = "ab" Вывод: [0, 1, 2] Объяснение: Подстроки "ab", "ba", "ab" являются анаграммами "ab"
Ограничения:
💡 Подсказка: Окно фиксированного размера len(p). Сравнивайте Counter окна с Counter(p). Анаграмма = одинаковые частоты всех символов.
Решение:
from collections import Counter
def findAnagrams(s, p):
if len(s) < len(p):
return []
p_count = Counter(p)
window_count = Counter(s[:len(p)])
result = []
if p_count == window_count:
result.append(0)
for i in range(len(p), len(s)):
# Добавляем s[i]
window_count[s[i]] += 1
# Удаляем s[i - len(p)]
window_count[s[i - len(p)]] -= 1
if window_count[s[i - len(p)]] == 0:
del window_count[s[i - len(p)]]
# Сравниваем с p
if window_count == p_count:
result.append(i - len(p) + 1)
return resultОбъяснение:
Сложность:
Условие:
Дана строка s, состоящая из заглавных английских букв, и целое число k. Вы можете заменить любой символ строки на любой другой заглавный английский символ не более k раз.
Найдите длину самой длинной подстроки, содержащей только одинаковые символы, после выполнения не более k замен.
Примеры:
Ввод: s = "ABAB", k = 2 Вывод: 4 Объяснение: Замените оба 'A' на 'B' (или наоборот), получится "BBBB"
Ввод: s = "AABABBA", k = 1 Вывод: 4 Объяснение: Замените средний 'A' на 'B', получится "AABBBBA"
Ограничения:
💡 Подсказка: max_count — частота самого частого символа в окне. (window_size - max_count) — сколько символов нужно заменить. Если замен > k — сжимайте окно.
Решение:
def characterReplacement(s, k):
count = {}
max_count = 0 # Максимальная частота одного символа в окне
left = 0
result = 0
for right in range(len(s)):
count[s[right]] = count.get(s[right], 0) + 1
max_count = max(max_count, count[s[right]])
# Если замен нужно больше k — сжимаем окно
# (right - left + 1) - max_count = сколько символов нужно заменить
while (right - left + 1) - max_count > k:
count[s[left]] -= 1
left += 1
result = max(result, right - left + 1)
return resultОбъяснение:
max_count — частота самого частого символа в окне(window_size - max_count) — сколько символов нужно заменитьmax_count не уменьшается при сжатии — это оптимизация, не влияющая на результат (окно не уменьшится меньше уже найденного максимума)Сложность:
Условие:
Даны две строки s1 и s2. Верните true, если s2 содержит перестановку s1 в качестве подстроки.
Другими словами, существует ли подстрока в s2, которая является анаграммой s1?
Примеры:
Ввод: s1 = "ab", s2 = "eidbaooo" Вывод: true Объяснение: s2 содержит "ba" (перестановка "ab")
Ввод: s1 = "ab", s2 = "eidboaoo" Вывод: false
Ограничения:
💡 Подсказка: Окно фиксированного размера len(s1). Перестановка = те же символы с теми же частотами. Сравнивайте Counter на каждом шаге.
Решение:
def checkInclusion(s1, s2):
if len(s1) > len(s2):
return False
s1_count = Counter(s1)
window_count = Counter(s2[:len(s1)])
if s1_count == window_count:
return True
for i in range(len(s1), len(s2)):
# Добавляем новый символ
window_count[s2[i]] += 1
# Удаляем старый
window_count[s2[i - len(s1)]] -= 1
if window_count[s2[i - len(s1)]] == 0:
del window_count[s2[i - len(s1)]]
if window_count == s1_count:
return True
return FalseОбъяснение:
Сложность:
Условие:
Дан массив положительных целых чисел nums и положительное целое число target. Найдите минимальную длину непрерывного подмассива, сумма которого больше или равна target.
Если такого подмассива нет, верните 0.
Примеры:
Ввод: target = 7, nums = [2, 3, 1, 2, 4, 3] Вывод: 2 Объяснение: Подмассив [4, 3] имеет минимальную длину 2
Ввод: target = 4, nums = [1, 4, 4] Вывод: 1
Ввод: target = 11, nums = [1, 1, 1, 1, 1, 1, 1, 1] Вывод: 0
Ограничения:
💡 Подсказка: Расширяйте окно, накапливая сумму. Когда сумма ≥ target — сжимайте для минимизации длины. Обновляйте минимум на каждом шаге сжатия.
Решение:
def minSubArrayLen(target, nums):
left = 0
current_sum = 0
min_len = float('inf')
for right in range(len(nums)):
current_sum += nums[right]
# Сжимаем, пока сумма ≥ target
while current_sum >= target:
min_len = min(min_len, right - left + 1)
current_sum -= nums[left]
left += 1
return 0 if min_len == float('inf') else min_lenОбъяснение:
Сложность:
Условие:
Дан массив целых чисел nums и целое число k. Окно размера k скользит по массиву от левого края до правого.
Найдите максимальный элемент в каждом окне. Верните массив максимумов для всех окон.
Примеры:
Ввод: nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3 Вывод: [3, 3, 5, 5, 6, 7] Объяснение:
Ввод: nums = [1], k = 1 Вывод: [1]
Ограничения:
💡 Подсказка: Используйте монотонную deque (двустороннюю очередь), хранящую индексы в порядке убывания значений. dq[0] — индекс текущего максимума.
Решение (Monotonic Deque):
from collections import deque
def maxSlidingWindow(nums, k):
dq = deque() # Хранит индексы в порядке убывания значений
result = []
for i in range(len(nums)):
# Удаляем индексы, вышедшие из окна
if dq and dq[0] == i - k:
dq.popleft()
# Удаляем элементы, меньшие текущего (они не нужны)
while dq and nums[dq[-1]] < nums[i]:
dq.pop()
dq.append(i)
# Добавляем максимум окна в результат
if i >= k - 1:
result.append(nums[dq[0]]) # dq[0] — индекс максимума
return resultОбъяснение:
deque хранит индексы в порядке убывания значенийdq[0] — индекс текущего максимумаnums[i] удаляем все меньшие элементы (они бесполезны)Почему это работает?
dq[0]Сложность:
Условие:
Дан целый массив fruits, где fruits[i] — тип фрукта на i-м дереве.
У вас есть две корзины, и каждая корзина может содержать только один тип фруктов. Тип фруктов не ограничен.
Начиная с любого дерева, вы должны собрать ровно один фрукт с каждого дерева подряд (включая стартовое), пока не встретите фрукт, который не помещается в ваши корзины.
Найдите максимальное количество фруктов, которое вы можете собрать.
Примеры:
Ввод: fruits = [1, 2, 1] Вывод: 3 Объяснение: Можно собрать все три фрукта
Ввод: fruits = [0, 1, 2, 2] Вывод: 3 Объяснение: Можно собрать [1, 2, 2]
Ввод: fruits = [1, 2, 3, 2, 2] Вывод: 4 Объяснение: Можно собрать [2, 3, 2, 2]
Ограничения:
💡 Подсказка: basket хранит частоты типов фруктов в окне. Если типов > 2 — сжимайте слева, пока не останется 2. Обновляйте максимум длины.
Решение:
def totalFruit(fruits):
basket = {}
left = 0
max_fruits = 0
for right in range(len(fruits)):
basket[fruits[right]] = basket.get(fruits[right], 0) + 1
# Если больше 2 типов — сжимаем
while len(basket) > 2:
basket[fruits[left]] -= 1
if basket[fruits[left]] == 0:
del basket[fruits[left]]
left += 1
max_fruits = max(max_fruits, right - left + 1)
return max_fruitsОбъяснение:
basket хранит частоты типов фруктов в окнеСложность:
Условие:
Дан массив целых чисел nums и целое число k. Подмассив называется «красивым» (nice), если он содержит ровно k нечётных чисел.
Верните количество красивых подмассивов.
Примеры:
Ввод: nums = [1, 1, 2, 1, 1], k = 3 Вывод: 2 Объяснение: Единственные подмассивы с 3 нечётными числами: [1, 1, 2, 1] и [1, 2, 1, 1]
Ввод: nums = [2, 4, 6], k = 1 Вывод: 0 Объяснение: Нет нечётных чисел
Ввод: nums = [2, 2, 2, 1, 2, 2, 1, 2, 2, 2], k = 2 Вывод: 16
Ограничения:
💡 Подсказка: temp_count хранит, сколько валидных окон заканчивается на right. Когда odd_count == k, сжимайте и считайте варианты.
Решение (Sliding Window):
def numberOfSubarrays(nums, k):
count = {0: 1} # prefix_sum -> count
odd_count = 0
result = 0
for num in nums:
if num % 2 == 1:
odd_count += 1
# Если есть префикс с odd_count - k, то подмассив между ними имеет k нечётных
if odd_count - k in count:
result += count[odd_count - k]
count[odd_count] = count.get(odd_count, 0) + 1
return resultИли чистый Sliding Window:
def numberOfSubarrays(nums, k):
left = 0
odd_count = 0
result = 0
temp_count = 0 # Количество валидных окон с текущим right
for right in range(len(nums)):
if nums[right] % 2 == 1:
odd_count += 1
temp_count = 0
# Сжимаем, пока нечётных = k
while odd_count == k:
temp_count += 1
if nums[left] % 2 == 1:
odd_count -= 1
left += 1
result += temp_count
return resultОбъяснение:
temp_count хранит, сколько валидных окон заканчивается на rightodd_count == k, сжимаем и считаем вариантыodd_count > k, temp_count сбрасываетсяСложность:
Условие:
Даны две строки s и t одинаковой длины и целое число maxCost.
Стоимость изменения s[i] в t[i] равна |s[i] - t[i]| (абсолютная разница ASCII-кодов).
Найдите максимальную длину подстроки строки s, которую можно преобразовать в соответствующую подстроку строки t с общей стоимостью не более maxCost.
Примеры:
Ввод: s = "abcd", t = "bcdf", maxCost = 3 Вывод: 3 Объяснение: "abc" из s может быть изменено в "bcd" стоимостью 3
Ввод: s = "abcd", t = "cdef", maxCost = 3 Вывод: 1 Объяснение: Один символ из s может быть изменён в соответствующий символ из t стоимостью 1
Ограничения:
💡 Подсказка: Стоимость окна = сумма стоимостей изменений символов. Расширяйте окно, накапливая стоимость. Если стоимость > maxCost — сжимайте.
Решение:
def equalSubstring(s, t, maxCost):
left = 0
current_cost = 0
max_len = 0
for right in range(len(s)):
current_cost += abs(ord(s[right]) - ord(t[right]))
# Сжимаем, пока стоимость > бюджета
while current_cost > maxCost:
current_cost -= abs(ord(s[left]) - ord(t[left]))
left += 1
max_len = max(max_len, right - left + 1)
return max_lenОбъяснение:
Сложность:
Условие:
Дан бинарный массив nums. Необходимо удалить ровно один элемент из массива.
Найдите длину самой длинной непустой подстроки, содержащей только единицы, после удаления.
Если в массиве нет единиц, верните 0.
Примеры:
Ввод: nums = [1, 1, 0, 1] Вывод: 3 Объяснение: После удаления 0 на позиции 2 получаем [1, 1, 1]
Ввод: nums = [0, 1, 1, 1, 0, 1, 1, 0, 1] Вывод: 5 Объяснение: После удаления 0 на позиции 4 получаем 5 единиц подряд
Ввод: nums = [1, 1, 1] Вывод: 2 Объяснение: Должны удалить один элемент, остаётся 2 единицы
Ограничения:
💡 Подсказка: Допускайте максимум 1 ноль в окне (его удалите). Длина результата = right - left (без +1, так как один элемент удаляем). Если все единицы — возвращайте n-1.
Решение:
def longestSubarray(nums):
left = 0
zero_count = 0
max_len = 0
for right in range(len(nums)):
if nums[right] == 0:
zero_count += 1
# Если нулей больше 1 — сжимаем
while zero_count > 1:
if nums[left] == 0:
zero_count -= 1
left += 1
# Длина подстроки из 1 = окно - 1 (удаляем один элемент)
max_len = max(max_len, right - left)
# Особый случай: все единицы — всё равно удаляем одну
return max_len if max_len < len(nums) else len(nums) - 1Объяснение:
right - left (без +1, так как один элемент удаляем)Сложность:
Проблема: Сжатие окна происходит слишком рано или поздно.
# ❌ Неправильно — сжимаем слишком рано
while left < right: # Должно быть по условию задачи!
window_state[s[left]] -= 1
left += 1
# ✅ Правильно — сжимаем, пока условие не выполнено
while not valid_window(window_state):
window_state[s[left]] -= 1
left += 1Почему это неправильно: Условие left < right не гарантирует, что окно валидно. Нужно проверять конкретное условие задачи (например, количество уникальных символов).
Как обнаружить: Проверьте, что после сжатия окно действительно удовлетворяет условию задачи.
Проблема: Результат обновляется не в том месте.
# ❌ Неправильно — обновляем только после сжатия
for right in range(len(s)):
window_state[s[right]] += 1
while not valid():
shrink()
# Пропущено обновление result!
# ✅ Правильно — обновляем после каждого шага
for right in range(len(s)):
window_state[s[right]] += 1 # expand
while not valid():
shrink()
result = max(result, right - left + 1) # обновляем ответПочему это неправильно: Максимальная длина может быть достигнута в любой момент, а не только после сжатия.
Как обнаружить: Убедитесь, что result = max(result, ...) стоит после цикла while.
Проблема: left может стать больше right.
# ❌ Неправильно — может быть left > right
while condition:
left += 1
# left может стать > right!
# ✅ Правильно — проверяем границы
while left <= right and condition:
left += 1Почему это неправильно: При left > right окно становится некорректным (отрицательная длина).
Как обнаружить: Всегда добавляйте проверку left <= right в условие цикла.
Проблема: Ключ остаётся в словаре с нулевым значением.
# ❌ Неправильно — ключ остаётся с 0
window_state[s[left]] -= 1
# window_state = {'a': 0, 'b': 1} — 'a' всё ещё в словаре!
# ✅ Правильно — удаляем ключ при 0
window_state[s[left]] -= 1
if window_state[s[left]] == 0:
del window_state[s[left]]
# window_state = {'b': 1} — корректноПочему это неправильно: При сравнении словарей или проверке условий ключ с 0 может дать неверный результат.
Как обнаружить: Проверяйте, удаляются ли ключи при достижении 0.
Проблема: В задаче Longest Repeating Character Replacement max_count не уменьшается при сжатии.
# ❌ Неправильно — пытаемся уменьшить max_count
while (right - left + 1) - max_count > k:
count[s[left]] -= 1
max_count = max(count.values()) # O(n) — медленно!
left += 1
# ✅ Правильно — max_count не уменьшается (оптимизация)
while (right - left + 1) - max_count > k:
count[s[left]] -= 1
left += 1
# max_count остаётся максимальным за всё времяПочему это правильно: Нас интересует максимальное окно, а не текущее. Если max_count был больше, окно всё равно не станет больше уже найденного.
Как обнаружить: Это контринтуитивная оптимизация. Запомните: max_count только растёт.
Условие: Дан массив положительных целых чисел nums и положительное целое target. Найдите минимальную длину непрерывного подмассива, сумма которого больше или равна target.
Если такого подмассива нет, верните 0.
Пример:
Ввод: target = 7, nums = [2, 3, 1, 2, 4, 3]
Вывод: 2
Объяснение: Подмассив [4, 3] имеет минимальную длину 2
Используйте скользящее окно с двумя указателями. Расширяйте окно, накапливая сумму.
Когда сумма становится >= target, сжимайте окно слева для минимизации длины.
Обновляйте минимальную длину на каждом шаге сжатия: min_len = min(min_len, right - left + 1).
def minSubArrayLen(target, nums):
left = 0
current_sum = 0
min_len = float('inf')
for right in range(len(nums)):
current_sum += nums[right] # Расширяем
# Сжимаем, пока сумма >= target
while current_sum >= target:
min_len = min(min_len, right - left + 1)
current_sum -= nums[left]
left += 1
return 0 if min_len == float('inf') else min_lenОбъяснение:
Сложность:
| Задача | Тип окна | Ключевая идея |
|---|---|---|
| Max Sum Subarray K | Фиксированное | Сдвиг: -arr[i-k] + arr[i] |
| Longest Unique Substring | Переменное | Set для уникальных |
| Minimum Window Substring | Переменное | Counter + need_count |
| Find All Anagrams | Фиксированное | Сравнение Counter |
| Character Replacement | Переменное | max_count не уменьшается |
| Sliding Window Maximum | Monotonic Deque | Deque хранит индексы |
| Min Size Subarray Sum | Переменное | Сумма ≥ target |
Sliding Window — мощнейший паттерн для оптимизации:
Ключ к успеху:
Вопросы ещё не добавлены
Вопросы для этой подтемы ещё не добавлены.