Sliding Window

Универсальная техника для задач на подстроки и подмассивы: окно «скользит» по данным, избегая пересчёта и обеспечивая сложность O(n)

#1. Суть паттерна

Sliding Window — это оптимизационная техника для задач, где требуется найти подстроку/подмассив с определёнными свойствами. Вместо перебора всех подстрок за O(n²), окно скользит по данным за O(n).

#1.1 Термины

Массив — упорядоченная коллекция элементов одного типа.

Подмассив — непрерывная часть массива (элементы идут подряд).

Подпоследовательность — элементы массива в том же порядке, но не обязательно непрерывные.

Подстрока — непрерывная часть строки.

Префикс — начало строки (подстрока, начинающаяся с первого символа).

Суффикс — конец строки (подстрока, заканчивающаяся последним символом).

Хэш-функция — функция, преобразующая входные данные в число (хэш).

Хэш-таблица — структура данных для быстрого поиска по ключу (в среднем O(1)).

Коллизия — ситуация, когда два разных ключа дают одинаковый хэш.

Палиндром — строка, читающаяся одинаково слева направо и справа налево.

Анаграмма — строка, полученная перестановкой символов другой строки.

Подпоследовательность (строки) — строка, полученная удалением нуля или более символов без изменения порядка остальных.

#Когда применять

✅ Подстрока/подмассив — найти минимальную/максимальную длину
✅ Сумма/произведение — найти подмассив с суммой ≥ target
✅ Уникальные символы — longest substring without repeating
✅ Сравнение частот — найти все анаграммы
✅ Фиксированный размер — максимум в окне размера k

#Типы окон

Тип	Описание	Пример
Фиксированный размер	Окно всегда k элементов	Maximum Sum Subarray of Size K
Переменный размер	Окно расширяется/сжимается по условию	Longest Substring Without Repeating
Два окна	Одновременно два окна	Permutation in String

#2. Базовый шаблон: переменное окно

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 result

#Как это работает

Расширяем (right += 1): добавляем элемент в окно
Проверяем условие: если нарушено — сжимаем
Сжимаем (left += 1): удаляем элементы слева, пока условие не выполнится
Обновляем ответ: текущее окно валидно — считаем длину/сумму

#3. Шаблон: фиксированное окно

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

#4. Разбор задач

#Задача 1: Maximum Sum Subarray of Size K (LeetCode — аналог) 🟩 Easy

Ссылка: — (аналог 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

Ограничения:

1 <= arr.length <= 10⁵
1 <= k <= arr.length
arr[i] — целые числа

💡 Подсказка: Вычислите сумму первого окна размера 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

Объяснение:

Вычисляем сумму первого окна [0, k-1]
На каждом шаге сдвигаем окно: вычитаем уходящий элемент, добавляем новый
Обновляем максимум

Сложность:

Время: O(k) + O(n-k) = O(n)
Память: O(1)

#Задача 2: Longest Substring Without Repeating Characters (LeetCode 3) 🟩 Medium

Ссылка: https://leetcode.com/problems/longest-substring-without-repeating-characters/

Условие: Дана строка s. Найдите длину самой длинной подстроки, не содержащей повторяющихся символов.

Примеры:

Ввод: s = "abcabcbb" Вывод: 3 Объяснение: Подстрока "abc" имеет длину 3

Ввод: s = "bbbbb" Вывод: 1 Объяснение: Подстрока "b" имеет длину 1

Ввод: s = "pwwkew" Вывод: 3 Объяснение: Подстрока "wke" имеет длину 3

Ограничения:

0 <= s.length <= 5 × 10⁴
s состоит из английских букв, цифр, символов и пробелов

💡 Подсказка: Используйте 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

Сложность:

Время: O(n) — каждый символ добавляется и удаляется максимум once
Память: O(min(n, |alphabet|))

#Задача 3: Minimum Window Substring (LeetCode 76) 🔴 Hard

Ссылка: https://leetcode.com/problems/minimum-window-substring/

Условие: Даны две строки s и t. Найдите минимальную подстроку в s, которая содержит все символы из t (с учётом частоты каждого символа).

Если такой подстроки нет, верните пустую строку.

Гарантируется, что ответ уникален.

Примеры:

Ввод: s = "ADOBECODEBANC", t = "ABC" Вывод: "BANC" Объяснение: Минимальная подстрока, содержащая все символы "ABC"

Ввод: s = "a", t = "a" Вывод: "a"

Ввод: s = "a", t = "aa" Вывод: "" Объяснение: Нет подстроки, содержащей два символа 'a'

Ограничения:

m == s.length, n == t.length
1 <= m, n <= 10⁵
s и t состоят из английских букв

💡 Подсказка: Используйте 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 хранит, сколько каждого символа нужно из t
need_count — общее количество ещё не найденных символов
Расширяем окно, пока need_count > 0
Когда need_count == 0 — все символы найдены, сжимаем для минимизации
need[char] может быть отрицательным — это лишние символы

Сложность:

Время: O(n) — каждый символ обрабатывается дважды
Память: O(|alphabet|)

#Задача 4: Find All Anagrams in a String (LeetCode 438) 🟩 Medium

Ссылка: https://leetcode.com/problems/find-all-anagrams-in-a-string/

Условие: Даны две строки 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"

Ограничения:

1 <= s.length, p.length <= 3 × 10⁴
s и p состоят из строчных английских букв

💡 Подсказка: Окно фиксированного размера 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

Объяснение:

Окно фиксированного размера len(p)
Сравниваем Counter окна с Counter(p)
Анаграмма = одинаковые частоты всех символов

Сложность:

Время: O(n × |alphabet|) — сравнение Counter за O(|alphabet|)
Память: O(|alphabet|)

#Задача 5: Longest Repeating Character Replacement (LeetCode 424) 🟩 Medium

Ссылка: https://leetcode.com/problems/longest-repeating-character-replacement/

Условие: Дана строка s, состоящая из заглавных английских букв, и целое число k. Вы можете заменить любой символ строки на любой другой заглавный английский символ не более k раз.

Найдите длину самой длинной подстроки, содержащей только одинаковые символы, после выполнения не более k замен.

Примеры:

Ввод: s = "ABAB", k = 2 Вывод: 4 Объяснение: Замените оба 'A' на 'B' (или наоборот), получится "BBBB"

Ввод: s = "AABABBA", k = 1 Вывод: 4 Объяснение: Замените средний 'A' на 'B', получится "AABBBBA"

Ограничения:

1 <= s.length <= 10⁵
s состоит из заглавных английских букв
0 <= k <= s.length

💡 Подсказка: 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) — сколько символов нужно заменить
Если замен > k — сжимаем окно
Важно: max_count не уменьшается при сжатии — это оптимизация, не влияющая на результат (окно не уменьшится меньше уже найденного максимума)

Сложность:

Время: O(n)
Память: O(1) — максимум 26 символов

#Задача 6: Permutation in String (LeetCode 567) 🟩 Medium

Ссылка: https://leetcode.com/problems/permutation-in-string/

Условие: Даны две строки s1 и s2. Верните true, если s2 содержит перестановку s1 в качестве подстроки.

Другими словами, существует ли подстрока в s2, которая является анаграммой s1?

Примеры:

Ввод: s1 = "ab", s2 = "eidbaooo" Вывод: true Объяснение: s2 содержит "ba" (перестановка "ab")

Ввод: s1 = "ab", s2 = "eidboaoo" Вывод: false

Ограничения:

1 <= s1.length, s2.length <= 10⁴
s1 и s2 состоят из строчных английских букв

💡 Подсказка: Окно фиксированного размера 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

Объяснение:

Окно фиксированного размера len(s1)
Перестановка = те же символы с теми же частотами
Сравниваем Counter на каждом шаге

Сложность:

Время: O(n × |alphabet|)
Память: O(|alphabet|)

#Задача 7: Minimum Size Subarray Sum (LeetCode 209) 🟩 Medium

Ссылка: https://leetcode.com/problems/minimum-size-subarray-sum/

Условие: Дан массив положительных целых чисел 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

Ограничения:

1 <= target <= 10⁹
1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁵

💡 Подсказка: Расширяйте окно, накапливая сумму. Когда сумма ≥ 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

Объяснение:

Расширяем окно, накапливая сумму
Когда сумма ≥ target — сжимаем для минимизации длины
Обновляем минимум на каждом шаге сжатия

Сложность:

Время: O(n) — каждый элемент добавляется и удаляется once
Память: O(1)

#Задача 8: Sliding Window Maximum (LeetCode 239) 🔴 Hard

Ссылка: https://leetcode.com/problems/sliding-window-maximum/

Условие: Дан массив целых чисел nums и целое число k. Окно размера k скользит по массиву от левого края до правого.

Найдите максимальный элемент в каждом окне. Верните массив максимумов для всех окон.

Примеры:

Ввод: nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3 Вывод: [3, 3, 5, 5, 6, 7] Объяснение:

Окно [1, 3, -1] → max = 3
Окно [3, -1, -3] → max = 3
Окно [-1, -3, 5] → max = 5
и т.д.

Ввод: nums = [1], k = 1 Вывод: [1]

Ограничения:

1 <= nums.length <= 10⁵
-10⁴ <= nums[i] <= 10⁴
1 <= k <= nums.length

💡 Подсказка: Используйте монотонную 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] удаляем все меньшие элементы (они бесполезны)
Удаляем индексы, вышедшие за пределы окна

Почему это работает?

Элементы в deque монотонно убывают
Максимум всегда на позиции dq[0]
Каждый элемент добавляется и удаляется максимум once

Сложность:

Время: O(n) — амортизированно
Память: O(k)

#Задача 9: Fruit Into Baskets (LeetCode 904) 🟩 Medium

Ссылка: https://leetcode.com/problems/fruit-into-baskets/

Условие: Дан целый массив 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]

Ограничения:

1 <= fruits.length <= 10⁵
0 <= fruits[i] < fruits.length

💡 Подсказка: 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 хранит частоты типов фруктов в окне
Если типов > 2 — сжимаем слева, пока не останется 2
Обновляем максимум длины

Сложность:

Время: O(n)
Память: O(1) — максимум 3 типа в словаре

#Задача 10: Count Number of Nice Subarrays (LeetCode 1248) 🟩 Medium

Ссылка: https://leetcode.com/problems/count-number-of-nice-subarrays/

Условие: Дан массив целых чисел 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

Ограничения:

1 <= nums.length <= 50000
0 <= nums[i] <= 10⁵
1 <= k <= nums.length

💡 Подсказка: 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 хранит, сколько валидных окон заканчивается на right
Когда odd_count == k, сжимаем и считаем варианты
Когда odd_count > k, temp_count сбрасывается

Сложность:

Время: O(n)
Память: O(1)

#Задача 11: Get Equal Substrings Within Budget (LeetCode 1208) 🟩 Medium

Ссылка: https://leetcode.com/problems/get-equal-substrings-within-budget/

Условие: Даны две строки 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

Ограничения:

1 <= s.length == t.length <= 10⁵
0 <= maxCost <= 10⁶
s и t состоят из строчных английских букв

💡 Подсказка: Стоимость окна = сумма стоимостей изменений символов. Расширяйте окно, накапливая стоимость. Если стоимость > 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

Объяснение:

Стоимость окна = сумма стоимостей изменений символов
Расширяем окно, накапливая стоимость
Если стоимость > maxCost — сжимаем

Сложность:

Время: O(n)
Память: O(1)

#Задача 12: Longest Subarray of 1's After Deleting One Element (LeetCode 1493) 🟩 Medium

Ссылка: https://leetcode.com/problems/longest-subarray-of-1s-after-deleting-one-element/

Условие: Дан бинарный массив 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 <= nums.length <= 10⁵
nums[i] равно 0 или 1

💡 Подсказка: Допускайте максимум 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

Объяснение:

Допускаем максимум 1 ноль в окне (его удалим)
Длина результата = right - left (без +1, так как один элемент удаляем)
Если все единицы — возвращаем n-1

Сложность:

Время: O(n)
Память: O(1)

#5. ⚠️ Common Mistakes

#❌ Ошибка 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 не гарантирует, что окно валидно. Нужно проверять конкретное условие задачи (например, количество уникальных символов).

Как обнаружить: Проверьте, что после сжатия окно действительно удовлетворяет условию задачи.

#❌ Ошибка 2: Забыли обновить ответ

Проблема: Результат обновляется не в том месте.

# ❌ Неправильно — обновляем только после сжатия
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.

#❌ Ошибка 3: Неправильная обработка пустого окна

Проблема: left может стать больше right.

# ❌ Неправильно — может быть left > right
while condition:
    left += 1
    # left может стать > right!

# ✅ Правильно — проверяем границы
while left <= right and condition:
    left += 1

Почему это неправильно: При left > right окно становится некорректным (отрицательная длина).

Как обнаружить: Всегда добавляйте проверку left <= right в условие цикла.

#❌ Ошибка 4: Неправильное удаление из Counter/словаря

Проблема: Ключ остаётся в словаре с нулевым значением.

# ❌ Неправильно — ключ остаётся с 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.

#❌ Ошибка 5: max_count не обновляется при сжатии (Character Replacement)

Проблема: В задаче 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 только растёт.

#6. 🎯 Попробуйте сами

#Задача для самостоятельного решения

Условие: Дан массив положительных целых чисел nums и положительное целое target. Найдите минимальную длину непрерывного подмассива, сумма которого больше или равна target.

Если такого подмассива нет, верните 0.

Пример:

Ввод: target = 7, nums = [2, 3, 1, 2, 4, 3]
Вывод: 2
Объяснение: Подмассив [4, 3] имеет минимальную длину 2

💡 Подсказка 1

Используйте скользящее окно с двумя указателями. Расширяйте окно, накапливая сумму.

💡 Подсказка 2

Когда сумма становится >= target, сжимайте окно слева для минимизации длины.

💡 Подсказка 3

Обновляйте минимальную длину на каждом шаге сжатия: 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

Объяснение:

Расширяем окно, накапливая сумму
Когда сумма >= target — сжимаем для минимизации
Обновляем минимум на каждом шаге сжатия

Сложность:

Время: O(n) — каждый элемент добавляется и удаляется один раз
Память: O(1)

#7. Шпаргалка

Задача	Тип окна	Ключевая идея
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

#7. Заключение

Sliding Window — мощнейший паттерн для оптимизации:

Перебор всех подстрок O(n²) → скользящее окно O(n)
Применим к десяткам задач на строки и массивы
Сочетается с Hash Map, Counter, Deque

Ключ к успеху:

Определить тип окна (фиксированное/переменное)
Выбрать структуру для состояния окна (set, dict, deque)
Правильно определить условие сжатия

Тип

Описание

Пример

Фиксированный размер

Окно всегда k элементов

Maximum Sum Subarray of Size K

Переменный размер

Окно расширяется/сжимается по условию

Longest Substring Without Repeating

Два окна

Одновременно два окна

Permutation in String

Задача

Тип окна

Ключевая идея

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