一文搞懂滑动窗口：定长与可变窗口模板

为什么连续子数组问题总该先想到滑动窗口

很多数组或字符串题都包含“连续”“最长”“最短”“至多”“恰好”等关键词。如果直接枚举所有区间，通常需要枚举左右端点，再扫描区间内容，时间复杂度很容易达到 O(n²) 甚至 O(n³)。滑动窗口本质上是一种用双指针维护合法区间的技巧：右指针负责扩展窗口，左指针负责收缩窗口，在一次遍历中完成候选答案的维护。

它能成立的关键在于单调性：窗口向右移动时，如果当前窗口已经不合法，继续扩大右边界通常不会重新变合法；反过来，如果要求窗口内字符种类不超过 k，左边界收缩只会让限制更容易满足。具备这种“扩张—收缩”单调关系的问题，才能安全使用滑动窗口。

定长窗口与可变窗口怎么选

定长窗口适用于窗口大小固定的问题，例如“长度为 k 的子数组最大平均数”“字符串排列”“大小为 K 的不同数字个数”。写法重点是先加入右侧元素，再在窗口长度达到 k 时更新答案并移出最左侧元素。

可变窗口适用于窗口长度不固定的问题，例如“无重复字符的最长子串”“长度最小的子数组”“至多包含 K 个不同字符的最长子串”。写法重点是用右指针不断扩张，当窗口不合法或满足条件时，移动左指针收缩，并在合适位置更新答案。

定长滑动窗口模板：先入窗，再补齐，最后出窗

定长窗口最稳定的模板不需要一开始单独构造前 k 个元素，而是让 right 从 0 遍历到末尾，每次加入当前元素。只要窗口长度大于 k，就持续移动 left；当窗口长度恰好等于 k 时，说明当前窗口已经成型，可以更新答案。

下面以“长度为 k 的子数组最大和”为例：

from typing import List


def max_sum_fixed_window(nums: List[int], k: int) -> int:
    if k <= 0 or k > len(nums):
        return 0

    window_sum = 0
    answer = float("-inf")
    left = 0

    for right, value in enumerate(nums):
        # 1. 右指针元素进入窗口
        window_sum += value

        # 2. 窗口尚未达到固定长度时，只扩张，不更新答案
        if right - left + 1 < k:
            continue

        # 3. 窗口长度恰好为 k，更新答案
        answer = max(answer, window_sum)

        # 4. 左指针元素离开窗口，为下一轮做准备
        window_sum -= nums[left]
        left += 1

    return int(answer)


# 示例：长度为 3 的子数组最大和为 6，来自 [1, 2, 3]
print(max_sum_fixed_window([1, 2, 3, -10, 2, 1], 3))

每个元素最多进入窗口一次、离开窗口一次，因此时间复杂度为 O(n)，额外空间复杂度为 O(1)。

这个模板还可以直接迁移到字符串排列问题：用频数字典记录窗口内字符，当窗口长度等于目标字符串长度时，比较两个频次表是否相同。若每次都整体比较字典，字符集较大时可能引入 O(k) 比较成本；更常见的优化是维护 matches，表示有多少种字符的频次已经匹配，将比较降为 O(1)。

可变滑动窗口模板：扩张到越界，再收缩到合法

可变窗口没有固定长度，核心是维护窗口状态与一个合法性判断。以“和至少为 target 的最短连续子数组”为例，右指针不断加入数字，一旦窗口和达到目标，就尝试收缩左边界，在所有合法窗口中寻找最短长度。

from typing import List


def min_sub_array_len(target: int, nums: List[int]) -> int:
    window_sum = 0
    left = 0
    answer = float("inf")

    for right, value in enumerate(nums):
        # 右边界扩张
        window_sum += value

        # 只要窗口仍满足条件，就持续收缩，寻找更短答案
        while window_sum >= target:
            answer = min(answer, right - left + 1)
            window_sum -= nums[left]
            left += 1

    return 0 if answer == float("inf") else int(answer)


# 示例：和至少为 7 的最短子数组是 [4, 3]，长度为 2
print(min_sub_array_len(target=7, nums=[2, 3, 1, 2, 4, 3]))

时间复杂度仍然是 O(n)，因为 left 与 right 都只会从左向右移动；空间复杂度为 O(1)。

再看“无重复字符的最长子串”，它维护的不再是和，而是窗口内字符频次：

def length_of_longest_substring(s: str) -> int:
    freq = {}
    left = 0
    answer = 0

    for right, ch in enumerate(s):
        freq[ch] = freq.get(ch, 0) + 1

        # 出现重复字符时，窗口不合法，需要收缩
        while freq[ch] > 1:
            left_char = s[left]
            freq[left_char] -= 1
            left += 1

        # 此时 [left, right] 一定无重复字符
        answer = max(answer, right - left + 1)

    return answer


# 示例：最长无重复子串为 "abc"，长度为 3
print(length_of_longest_substring("abcbac"))

如果字符集固定，频次数组也可以替代字典；若输入是任意 Unicode 字符，字典更通用。该算法时间复杂度为 O(n)，空间复杂度为 O(k)，其中 k 是窗口内不同字符数量，最坏为字符集大小。

高频实战题：至多 K 个不同字符的最长子串

这道题同时考察双指针、频数字典和窗口合法性。右指针加入字符后，如果不同字符数量超过 k，就不断移动左指针，直到窗口重新合法。

def length_of_longest_substring_k_distinct(s: str, k: int) -> int:
    if k <= 0:
        return 0

    freq = {}
    left = 0
    answer = 0

    for right, ch in enumerate(s):
        freq[ch] = freq.get(ch, 0) + 1

        # 不同字符数超过 k，收缩到合法为止
        while len(freq) > k:
            left_char = s[left]
            freq[left_char] -= 1

            # 计数为 0 后必须删除，否则 len(freq) 不等于不同字符数
            if freq[left_char] == 0:
                del freq[left_char]

            left += 1

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

    return answer


# 示例：至多 2 种字符时，"ece" 或 "cec" 长度均为 3
print(length_of_longest_substring_k_distinct("eceba", 2))

时间复杂度为 O(n)，空间复杂度为 O(k)。注意这里收缩条件使用 while len(freq) > k，不能写成 if。虽然本题每次加入一个字符最多只可能新增一种字符，看似 if 也能删掉一种多余字符，但在更复杂的状态更新中，while 能保证循环结束时窗口必然合法，模板更安全。

“恰好”类问题为什么常转换成两次至多

“恰好包含 k 个不同字符的子数组数量”不能直接让窗口维持在“恰好 k”，因为右指针扩张过程中，窗口可能从少于 k 突然超过 k，左指针也可能存在多个可停留位置。更稳妥的方法是做差：

from collections import defaultdict
from typing import List


def at_most_k_positive(nums: List[int], k: int) -> int:
    freq = defaultdict(int)
    left = 0
    distinct = 0
    count = 0

    for right, value in enumerate(nums):
        if freq[value] == 0:
            distinct += 1
        freq[value] += 1

        while distinct > k:
            freq[nums[left]] -= 1
            if freq[nums[left]] == 0:
                distinct -= 1
            left += 1

        # 以 right 结尾、且不同正数个数不超过 k 的子数组数量
        count += right - left + 1

    return count


def exactly_k_positive(nums: List[int], k: int) -> int:
    # 恰好 k 个 = 至多 k 个 - 至多 k-1 个
    return at_most_k_positive(nums, k) - at_most_k_positive(nums, k - 1)

两次滑动窗口的总时间复杂度仍是 O(n)，空间复杂度为 O(k)。这类转换在“恰好 K 个不同整数”“恰好 K 个奇数”等计数题中非常常见。

避坑总结：模板之外最容易错的 5 个细节

第一，更新答案的位置不要搞反。求最长合法子串时，通常在窗口收缩合法之后更新；求最短合法子数组时，应在 while 内部、每收缩一次就更新，否则会漏掉更短窗口。常见错误现象是答案总是偏大，原因是只在右指针扩张后计算了一次长度。

第二，移除元素时要先更新状态，再执行 left += 1。例如窗口求和应先 window_sum -= nums[left]，字符频次应先减少 s[left]，再移动左指针。顺序写反会删除错误位置的元素，导致负数、频次不归零或重复字符判断失效。

第三，频次降为 0 后要根据状态设计删除或额外计数。若使用 len(freq) 表示不同字符数，必须 del freq[ch]；若保留键值为 0，则应维护 distinct，不能再用字典长度。典型报错是窗口明明只有两个字符，len(freq) 却始终大于 k。

第四，不要对缺少单调性的问题滥用滑动窗口。如果窗口内同时存在正数和负数，并且目标是“和等于 target 的子数组数量”，扩大窗口不一定让和变大，收缩窗口也不一定让和变小，此时应考虑前缀和加哈希表，而不是双指针。

第五，注意边界与循环条件。定长窗口要处理 k > len(nums)、k <= 0；可变窗口要确认答案不存在时返回 0 还是 -1。此外，收缩条件优先使用 while 保证窗口合法，不要为了代码短盲目改成 if。

掌握滑动窗口的关键不是背某一道题，而是识别三件事：窗口状态是什么、窗口合法条件是什么、答案应在收缩前还是收缩后更新。只要这三个问题回答清楚，定长窗口与可变窗口都可以稳定落到同一套双指针框架中。

免责声明

本工具与文章内容仅用于学习测试场景，优化建议仅供参考，请勿直接用于生产环境，由此产生的风险自行承担。