滑动窗口算法

子数组 / 子串问题的优化框架

核心思想： 维护一个动态窗口，通过移动左右边界减少重复计算

难度等级： 入门进阶

时间复杂度： O(n) 每个元素至多被访问两次

关键词： 滑动窗口、Sliding Window、定长窗口、变长窗口、双指针、队列、子串、子数组、O(n)

一、算法概述

滑动窗口（Sliding Window） 是一种在数组或字符串中高效处理连续子序列（子数组 / 子串）问题的算法技巧。其核心思想是：维护一个动态窗口，通过移动窗口的左右边界来遍历所有可能的连续区间，同时避免对重叠部分的重复计算。

暴力解法通常需要两层循环枚举所有起点和终点，时间复杂度为 O(n^2) 甚至 O(n^3)。滑动窗口通过"复用"窗口内的计算结果，将时间复杂度降低到 O(n)。

核心思想：

维护窗口： 用左右指针（或索引）定义当前处理的连续区间 [left, right]
减少重复计算： 窗口滑动时，只处理移入和移出的元素，而非重新计算整个区间
两种模式： 定长窗口（窗口大小固定）和变长窗口（窗口大小动态调整）
方向唯一： 左右指针都只向一个方向移动，不会回溯

算法框架模板（变长窗口通用）

Python

def sliding_window(s):
    # 初始化左右指针和窗口状态
    left = 0
    window = {}  # 或 collections.Counter() 等
    result = 0   # 或 [], 根据问题需要

    # right 指针逐步右移扩展窗口
    for right in range(len(s)):
        ch = s[right]
        # 将新字符加入窗口，更新窗口状态
        update(window, ch)

        # 当窗口不满足条件时，收缩左边界
        while shrink_condition(window):
            remove(window, s[left])
            left += 1

        # 此时窗口已满足条件，更新结果
        result = max(result, right - left + 1)
        # 或根据具体问题更新

    return result

这个通用框架可以解决绝大多数变长滑动窗口问题。关键在于三个部分：窗口状态的定义方式、收缩条件的判定逻辑、结果更新的时机。

二、定长滑动窗口

定长窗口 的窗口大小固定为 k，左右指针同步移动，每次右移一个单位。这种模式常用于计算固定大小子数组的最大值、最小值、平均值等问题。

2.1 固定大小窗口的基本模式

窗口从数组最左端开始，每次向右滑动一个位置。新旧窗口之间有 k-1 个重叠元素，因此只需处理一个元素的移入和一个元素的移出。

Python - 定长窗口模板

def fixed_window(nums, k):
    # 计算第一个窗口
    window_sum = sum(nums[:k])
    result = window_sum  # 或 max_result / min_result

    # 窗口向右滑动
    for i in range(k, len(nums)):
        # 移入新元素 nums[i]，移出旧元素 nums[i-k]
        window_sum += nums[i] - nums[i - k]
        result = max(result, window_sum)

    return result

2.2 典型问题：子数组最大平均数

LeetCode 643 —— 给定一个数组，找出所有大小为 k 的连续子数组的最大平均值。

Python - 最大平均数

def find_max_average(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]
        if window_sum > max_sum:
            max_sum = window_sum

    return max_sum / k  # 返回平均值

2.3 典型问题：长度为 K 的无重复字符子串

给定一个字符串和一个整数 k，找出所有长度为 k 且不含重复字符的子串数量。这道题将定长窗口与字符频率统计相结合。

Python - 定长 + 无重复字符

def num_k_len_no_repeat(s, k):
    if k > len(s):
        return 0

    count = [0] * 26
    unique = 0
    result = 0

    # 初始化第一个窗口
    for i in range(k):
        idx = ord(s[i]) - ord('a')
        if count[idx] == 0:
            unique += 1
        count[idx] += 1
    if unique == k:
        result += 1

    # 滑动窗口
    for i in range(k, len(s)):
        # 移出 left 字符
        left_idx = ord(s[i - k]) - ord('a')
        count[left_idx] -= 1
        if count[left_idx] == 0:
            unique -= 1

        # 移入 right 字符
        right_idx = ord(s[i]) - ord('a')
        if count[right_idx] == 0:
            unique += 1
        count[right_idx] += 1

        if unique == k:
            result += 1

    return result

定长窗口的特点

左右指针始终保持固定间距 k，同步移动
不需要 while 收缩循环，逻辑更简单
窗口状态更新公式：add(nums[right]) 和 remove(nums[right - k])
适用于：最大值、最小值、平均值、特定条件的计数等场景

三、变长滑动窗口

变长窗口 的窗口大小不固定，右指针不断向右扩展，当窗口不满足约束条件时，左指针向右收缩直到重新满足条件。这种模式是滑动窗口算法中最常用、最灵活的类型。

3.1 无重复字符的最长子串

LeetCode 3 —— 给定一个字符串，找出其中不含有重复字符的 最长子串 的长度。

Python - LeetCode 3

def length_of_longest_substring(s):
    # 用集合记录窗口内已出现的字符
    chars = set()
    left = 0
    max_len = 0

    for right in range(len(s)):
        # 如果 s[right] 已在窗口中，收缩左边界直到移除重复
        while s[right] in chars:
            chars.remove(s[left])
            left += 1

        # 将当前字符加入窗口
        chars.add(s[right])

        # 更新最大长度
        max_len = max(max_len, right - left + 1)

    return max_len

思路解析： 使用哈希集合 chars 维护当前窗口内的所有字符。右指针 right 逐个遍历字符，当遇到重复字符时，左指针 left 向右移动并移除集合中的字符，直到重复被消除。每一步都更新最大长度。

3.2 最小覆盖子串

LeetCode 76 —— 给定两个字符串 s 和 t，在 s 中找出包含 t 所有字符的 最短子串（难度：困难）。

Python - LeetCode 76

def min_window(s, t):
    if not s or not t:
        return ""

    # 统计 t 中各字符的需求量
    need = {}
    for ch in t:
        need[ch] = need.get(ch, 0) + 1

    # window 记录当前窗口中的字符计数
    window = {}
    left = 0
    valid = 0  # 记录已满足需求的字符种类数
    start, min_len = 0, float('inf')

    for right in range(len(s)):
        ch = s[right]
        if ch in need:
            window[ch] = window.get(ch, 0) + 1
            if window[ch] == need[ch]:
                valid += 1

        # 当所有字符种类都满足需求时，收缩窗口
        while valid == len(need):
            # 更新最短子串
            if right - left + 1 < min_len:
                start = left
                min_len = right - left + 1

            # 移出左边界字符
            d = s[left]
            left += 1
            if d in need:
                if window[d] == need[d]:
                    valid -= 1
                window[d] -= 1

    return s[start:start + min_len] if min_len != float('inf') else ""

最小覆盖子串的解题关键：

使用 need 字典记录目标串 t 中每个字符的需求量
使用 valid 变量统计有多少种字符的需求量已满足
当 valid == len(need) 时，说明窗口已完整覆盖 t
收缩左边界时同步更新 valid 和 window

3.3 长度最小的子数组

LeetCode 209 —— 给定一个正整数数组和一个目标值 target，找出满足元素和 >= target 的 最短连续子数组。

Python - LeetCode 209

def min_sub_array_len(target, nums):
    left = 0
    window_sum = 0
    min_len = float('inf')

    for right in range(len(nums)):
        # 扩展右边界
        window_sum += nums[right]

        # 当窗口和 >= target 时，收缩左边界
        while window_sum >= target:
            min_len = min(min_len, right - left + 1)
            window_sum -= nums[left]
            left += 1

    return 0 if min_len == float('inf') else min_len

3.4 至多包含 K 个不同字符的最长子串

LeetCode 340 —— 给定一个字符串，找出其中至多包含 k 个不同字符的 最长子串。

Python - LeetCode 340

def length_of_longest_substring_k_distinct(s, k):
    if k == 0 or not s:
        return 0

    window = {}
    left = 0
    max_len = 0

    for right in range(len(s)):
        # 将新字符加入窗口
        window[s[right]] = window.get(s[right], 0) + 1

        # 当不同字符数超过 k 时，收缩左边界
        while len(window) > k:
            window[s[left]] -= 1
            if window[s[left]] == 0:
                del window[s[left]]
            left += 1

        max_len = max(max_len, right - left + 1)

    return max_len

3.5 水果成篮

LeetCode 904 —— 你正在采摘水果，每棵树上的水果用整数表示类型。你有两个篮子，每个篮子只能装一种类型的水果。从任意位置开始，能连续采摘的最大水果数是多少？

Python - LeetCode 904 (至多2种不同元素)

def total_fruit(fruits):
    # 等价于：至多包含 2 种不同数字的最长连续子数组
    window = {}
    left = 0
    max_count = 0

    for right in range(len(fruits)):
        window[fruits[right]] = window.get(fruits[right], 0) + 1

        while len(window) > 2:
            window[fruits[left]] -= 1
            if window[fruits[left]] == 0:
                del window[fruits[left]]
            left += 1

        max_count = max(max_count, right - left + 1)

    return max_count

水果成篮问题是"至多包含 K 个不同字符"的特例（K=2），但它的描述角度很贴近实际生活场景，有助于理解滑动窗口的应用背景。

四、滑动窗口的扩展与收缩策略

理解 何时扩展右边界 和 何时收缩左边界 是掌握滑动窗口算法的关键。

4.1 右边界扩展条件

右指针 right 始终向前移动，每次迭代扩展一个元素。在每次扩展后，需要检查窗口是否仍然满足约束条件。右扩展是做"加法" —— 将新元素纳入窗口。

扩展右边界时要做的事情：
① 将 s[right] 纳入窗口状态（加入集合/增加计数/累加和）
② 更新窗口相关的辅助变量（valid / unique / sum 等）
③ 判断是否触发收缩条件

4.2 左边界收缩条件

左指针 left 在窗口不满足约束条件时向右移动，直到窗口重新满足条件。左收缩是做"减法" —— 移除窗口最左侧的元素。

收缩左边界时要做的事情：
① 将 s[left] 从窗口状态中移除（从集合删除/减少计数/减去值）
② 更新窗口相关的辅助变量
③ left 指针右移一位
④ 收缩是循环过程（while），可能一次移出多个元素

常见的收缩条件类型

和/积约束： 窗口元素和 >= target 时启动收缩（LeetCode 209）
字符去重约束： 遇到重复字符时启动收缩（LeetCode 3）
覆盖约束： 窗口已覆盖目标字符串所有字符时启动收缩（LeetCode 76）
种类约束： 窗口中不同字符数超过 k 时启动收缩（LeetCode 340）
频率约束： 某个字符出现频率超过限制时启动收缩

4.3 收缩时机的两种模式

模式一：收缩满足型

策略： 右指针不断扩展，直到窗口不再满足条件时启动收缩。

代表问题： 无重复字符最长子串（出现重复后才收缩）、至多 K 个不同字符（超过 K 后收缩）。

结果更新时机： 收缩完成后（此时窗口重新满足条件），更新结果。

模式二：收缩破坏型

策略： 右指针不断扩展，直到窗口满足条件时启动收缩。

代表问题： 最小覆盖子串（已覆盖 target 后收缩）、长度最小子数组（和 >= target 后收缩）。

结果更新时机： 收缩过程中（在收缩循环体内部），更新结果。

五、时间复杂度分析

滑动窗口算法的时间复杂度为 O(n)，其中 n 是数组或字符串的长度。这是滑动窗口最核心的优势之一。

为什么是 O(n)？

原因在于 每个元素至多进入窗口一次、离开窗口一次：

右指针 遍历整个数组，共移动 n 次 —— 贡献 O(n)
左指针 在最坏情况下也只会移动 n 次（每个元素至多被移出一次）—— 贡献 O(n)
左右指针合计移动不超过 2n 次，总时间复杂度 O(n)

注意：虽然左指针收缩时使用了 while 循环，但从整体来看，每次收缩操作移出的元素不会再被移入，因此总操作次数是线性的。这是滑动窗口与暴力解法的本质区别。

复杂度对比表

问题	暴力解法	滑动窗口	优化比
无重复字符最长子串	O(n^3)	O(n)	指数级提升
最小覆盖子串	O(n^3)	O(n)	指数级提升
长度最小子数组	O(n^2)	O(n)	线性提升
子数组最大平均数	O(n*k)	O(n)	倍数级提升
至多 K 个不同字符	O(n^2)	O(n)	线性提升

关于空间复杂度

滑动窗口的额外空间通常来自维护窗口状态的哈希表、集合或计数器。在最坏情况下，如果窗口中可能包含所有不重复的字符（例如字符串由全部 ASCII 字符组成），空间复杂度为 O(C)，其中 C 是字符集大小（对于英文字母是 26 或 52，对于 ASCII 是 128 或 256）。在大多数面试场景下，可视为 O(1) 额外空间。

六、滑动窗口 vs 双指针

滑动窗口和双指针（Two Pointers）是两种容易混淆的算法技巧。它们都使用两个指针来遍历数组，但 适用场景和指针移动方式 有本质区别。

对比维度	滑动窗口	双指针
区间性质	始终处理连续的子数组/子串	不要求连续，通常处理已排序数组
指针方向	左右指针同向移动，永不回头	两指针可相向移动（对撞指针）或同向（快慢指针）
典型问题	子串 / 子数组相关（覆盖、去重、最值）	两数之和、三数之和、盛水最多容器、删除有序数组重复项
数据结构	通常需要哈希表/计数器维护窗口内元素状态	通常不需要额外数据结构，直接比较指针指向的元素
移动逻辑	根据窗口的"约束条件"决定是否移动左指针	根据指针指向值的比较结果决定移动哪个指针
时间复杂度	O(n)	O(n)（排序后通常为 O(n log n)）
适用前提	处理连续子序列问题	数组通常需要提前排序

如何区分？

优先选择滑动窗口 的场景：问题涉及"子串"/"子数组"关键词，且要求计算某种连续区间上的最值或统计量。

优先选择双指针 的场景：问题涉及"两数之和"、"三数之和"、"移除元素"、"合并有序数组"等，需要在数组中搜索满足特定条件的元素对。

容易混淆的边界情况： LeetCode 11"盛最多水的容器"虽然用了左右指针，但属于对撞双指针而非滑动窗口 —— 两个指针从两端向中间移动，而非同向移动。

快慢指针 vs 滑动窗口

快慢指针（Floyd 判圈算法、删除有序数组重复项）也使用两个同向指针，但其核心是步速不同而非窗口概念。快慢指针通常用于环形检测或原地操作，不关注两个指针之间的"区间内容"，因此不属于滑动窗口。

七、队列实现滑动窗口

滑动窗口可以用 双端队列（Deque） 来实现，特别是在需要获取窗口内最大值或最小值的场景中。双端队列可以高效地从两端插入和删除元素。

7.1 滑动窗口最大值

LeetCode 239 —— 给定一个数组和一个大小为 k 的滑动窗口，返回每个窗口中 最大值 组成的数组。这是滑动窗口与单调队列结合的经典问题。

Python - LeetCode 239 (单调队列)

from collections import deque

def max_sliding_window(nums, k):
    if not nums or k == 0:
        return []

    dq = deque()  # 双端队列，存储索引，保持递减
    result = []

    for i in range(len(nums)):
        # 移除已离开窗口的索引（左边界收缩）
        while dq and dq[0] < i - k + 1:
            dq.popleft()

        # 维护单调递减队列：移除所有小于当前值的队尾元素
        while dq and nums[dq[-1]] < nums[i]:
            dq.pop()

        # 将当前索引加入队尾
        dq.append(i)

        # 当窗口形成后（i >= k-1），记录结果
        if i >= k - 1:
            result.append(nums[dq[0]])

    return result

单调队列的核心思想：

双端队列中存储的是元素索引而非元素值，便于判断元素是否已离开窗口
队列保持单调递减（从队首到队尾）：队首始终是当前窗口的最大值
每次新元素入队时，移除队尾所有小于它的元素 —— 因为这些"小元素"永远不可能再成为最大值
队首过期元素（索引 < i - k + 1）在每次迭代时从队首移除
时间复杂度：O(n)（每个元素入队一次、出队至多一次）

7.2 队列实现与双指针实现的对比

维度	双指针实现	双端队列实现
数据结构	两个整数指针（left, right）	双端队列（deque）
特点	直接管理窗口边界	能快速获取窗口内极值
适用问题	一般性滑动窗口（求和、计数、覆盖等）	需要窗口最值的问题（最大值、最小值）
空间复杂度	O(1) 辅助空间	O(k) 队列空间
实现难度	较低，模板化程度高	中等，需维护单调性

7.3 队列实现定长滑动窗口的通用模式

对于需要维护"窗口内极值信息"的定长窗口问题，单调双端队列是常用的优化手段。典型问题包括：

滑动窗口最大值（LeetCode 239）—— 维护单调递减队列
滑动窗口最小值（类似变形）—— 维护单调递增队列
绝对差不超过限制的最长连续子数组（LeetCode 1438）—— 维护两个单调队列

Python - LeetCode 1438 (双单调队列)

from collections import deque

def longest_subarray(nums, limit):
    # 维护单调递增队列（最小值）和单调递减队列（最大值）
    min_dq = deque()
    max_dq = deque()
    left = 0
    max_len = 0

    for right in range(len(nums)):
        # 维护最大值队列（递减）
        while max_dq and max_dq[-1] < nums[right]:
            max_dq.pop()
        max_dq.append(nums[right])

        # 维护最小值队列（递增）
        while min_dq and min_dq[-1] > nums[right]:
            min_dq.pop()
        min_dq.append(nums[right])

        # 如果最大值 - 最小值 > limit，收缩左边界
        while max_dq[0] - min_dq[0] > limit:
            if max_dq[0] == nums[left]:
                max_dq.popleft()
            if min_dq[0] == nums[left]:
                min_dq.popleft()
            left += 1

        max_len = max(max_len, right - left + 1)

    return max_len

八、核心要点总结

本质： 滑动窗口通过维护一个连续区间，复用重叠部分的计算结果，将 O(n^2) 问题优化为 O(n)
定长窗口： 左右指针固定间距同步移动，适用于固定大小子数组的统计问题（最大值、平均值等）
变长窗口： 右指针持续扩展，左指针按条件收缩，适用于满足约束的最优子串/子数组问题
收缩策略： "收缩满足型"（满足条件后更新结果）与"收缩破坏型"（收缩过程中更新结果）两种模式
时间复杂度： O(n)，每个元素至多入窗口一次、出窗口一次
与双指针区别： 滑动窗口关注窗口内部内容（连续区间），双指针关注元素对或位置关系（无需连续）
队列扩展： 维护窗口最值需要双端队列 + 单调性约束，典型应用是滑动窗口最大值
适用前提： 问题必须具有"单调性" —— 窗口扩展时条件变松，收缩时条件变严
常见误区： 滑动窗口适用于子数组/子串（连续），不适用于子序列（可以不连续）
调试技巧： 先写暴力解法验证正确性，再优化为滑动窗口；注意边界条件和窗口为空的情况

九、进一步思考

滑动窗口虽然强大，但并非万能。在掌握了基础用法之后，可以从以下几个方面进一步深入：

进阶方向一：多窗口 / 多条件

某些问题需要在一次遍历中维护多个窗口，或者窗口条件包含多个约束（如同时满足和与乘积限制）。这类问题需要更精细的状态管理。

进阶方向二：二维滑动窗口

在二维矩阵中应用滑动窗口思想，处理子矩阵问题。常见于图像处理（卷积操作）和二维前缀和优化。

进阶方向三：与二分查找结合

当滑动窗口的收缩条件具有单调性时，可以用二分查找优化左指针的收缩过程（虽然不会改变 O(n) 的渐进复杂度）。

进阶方向四：与数据结构结合

如 LeetCode 480"滑动窗口中位数"需要在滑动过程中维护窗口的有序性，这时需要结合堆（两个堆维护中位数）或平衡树等数据结构。

#	题目	难度	类型
643	子数组最大平均数 I	简单	定长窗口
3	无重复字符的最长子串	中等	变长窗口
209	长度最小的子数组	中等	变长窗口
904	水果成篮	中等	变长窗口（种类约束）
340	至多包含 K 个不同字符的最长子串	中等	变长窗口（种类约束）
76	最小覆盖子串	困难	变长窗口（覆盖约束）
239	滑动窗口最大值	困难	定长窗口 + 单调队列
1438	绝对差不超过限制的最长连续子数组	中等	变长窗口 + 双单调队列
480	滑动窗口中位数	困难	定长窗口 + 双堆
567	字符串的排列	中等	定长窗口（排列匹配）