Что такое sliding window?

Sliding window — техника для substring/subarray problems: поддержание «окна» [left, right], расширяющегося и сужающегося. O(n) без вложенных циклов.

# Fixed window размера k
def findMaxAverage(nums, k):
    window_sum = sum(nums[:k])
    max_sum = window_sum
    for i in range(k, len(nums)):
        window_sum += nums[i] - nums[i - k]
        max_sum = max(max_sum, window_sum)
    return max_sum / k

# Variable window — общий шаблон
left = 0
for right in range(len(s)):
    add s[right] to window
    while window_invalid:
        remove s[left]
        left += 1
    update result

Сужение (while) — O(n) total, не O(n²), т.к. left двигается только вперёд. Variable window: LeetCode 3, 76, 424. Важно: для subarray sum с negative numbers sliding window не работает (negative может «вылечить» при сужении) — использовать prefix sum или Kadane.