📈 FROM O(...) TO O(...) Скользящее окно: от O(n²) до O(n) Задача: найти максимальную сумму подмассива длиной k. nums = [2, 1, 5, 1, 3, 2] k = 3 # Ответ: 9 (подмассив [5, 1, 3]) Наивное решение: def max_sum(nums, k): max_s = 0 for i in range(len(nums) - k + 1): s = sum(nums[i:i+k]) max_s = max(max_s, s) return max_s sum() внутри цикла — пересчитываем окно целиком на каждом шаге. O(n·k). Скользящее окно: def max_sum(nums, k): window = sum(nums[:k]) max_s = window for i in range(k, len(nums)): window += nums[i] - nums[i - k] max_s = max(max_s, window) return max_s O(n) — один проход. Идея: не пересчитываем окно заново. Добавляем новый элемент справа, убираем старый слева. Одно сложение и одно вычитание вместо k операций. # [2, 1, 5] → сумма 8 # сдвиг: +1 -2 → [1, 5, 1] → сумма 7 # сдвиг: +3 -1 → [5, 1, 3] → сумма 9 ← максимум # сдвиг: +2 -5 → [1, 3, 2] → сумма 6 Когда применять: любая задача с подмассивом фиксированной длины — максимум, минимум, среднее, количество уникальных элементов. 🐍Вопросы с собесов -> ProstoPython