LeetCode（四）—— 滑动窗口技巧

如果你写过两层 for 循环去枚举所有连续子数组，那么滑动窗口多半就是你缺的那一步优化。它把 $O(nk)$ 或 $O(n^2)$ 的暴力枚举压成线性的一遍扫描，关键就在于"复用上一步算出来的东西"。本文从最朴素的直觉出发，先讲清楚思路，再用四道高频 LeetCode 题目把套路彻底落地，最后再补一个单调队列的进阶用法。

1. 一图看懂滑动窗口

滑动窗口本质上是数组或字符串上的一段连续区间 [left, right]。窗口移动的时候，我们不重新计算整个区间，而是把右边新进来的元素加进去、把左边离开的元素拿出来，每个元素最多被处理两次，整体是 $O(n)$。

按窗口大小是否变化，可以分成两类：

固定窗口——宽度固定为 k，左右指针同步前进。
可变窗口——right 主动扩张，left 在窗口"违反约束"时被动收缩。

下面这张图展示了固定窗口求最大子数组和：绿色是当前窗口，橙色是即将进入的元素，粉色是即将离开的元素。右侧的算式说明每次只做一次加法和一次减法，这就是滑动窗口的全部秘密。

2. 固定窗口：大小为 k 的最大子数组和

题目：给定数组 arr 和整数 k，求所有长度为 k 的连续子数组中和最大的那个。

朴素做法：枚举每个长度为 k 的切片再求和，复杂度 $O(nk)$。

滑动窗口：先算第一个窗口的和，之后每滑一格只做"减去离开者，加上进入者"。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
def max_sum_subarray(arr, k):
    """求长度为 k 的连续子数组的最大和。"""
    if len(arr) < k:
        return None

    window_sum = sum(arr[:k])     # 第一个窗口
    best = window_sum

    for right in range(k, len(arr)):
        # 进入：arr[right]   离开：arr[right - k]
        window_sum += arr[right] - arr[right - k]
        best = max(best, window_sum)

    return best

Java 版本

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
public int maxSumSubarray(int[] arr, int k) {
    if (arr.length < k) return Integer.MIN_VALUE;
    int windowSum = 0;
    for (int i = 0; i < k; i++) windowSum += arr[i];
    int best = windowSum;
    for (int right = k; right < arr.length; right++) {
        windowSum += arr[right] - arr[right - k];
        best = Math.max(best, windowSum);
    }
    return best;
}

复杂度：时间 $O(n)$，每滑一步只做常数次加减；空间 $O(1)$。

为什么能这么省？ 窗口的"和"只依赖窗口里的元素集合。当窗口右移一格，集合的变化恰好是"删一个、加一个"，所以只要把这两个变化量叠加就行了。这种增量更新的思路也适用于计数、频率表，乃至单调队列（见第 6 节）。

3. 可变窗口的两种姿势

如果窗口大小不固定，就要靠两个指针配合：

求最长合法窗口：right 一路向右扩张；一旦窗口违反约束，就把 left 往右挪到重新合法为止，期间记录最大长度。
求最短合法窗口：right 扩到窗口刚好满足条件后，left 尽量往右挤，看看能不能更短，每次收缩时更新答案。

下图追踪了"无重复字符的最长子串"在 "abcabcbb" 上的运行过程：绿色表示窗口合法、橙色括号是当前 [L, R]，粉色表示检测到重复，紫色表示正在收缩。

下面这张图把窗口长度随迭代步数的变化画了出来，绿色背景是扩张阶段，紫色是收缩阶段。

最关键的不变量是：left 永远只往右走，绝不回头。所以即使外层 for 套着内层 while，整个内层在全程里跑过的总步数也最多 $n$，这就是滑动窗口"摊还 $O(n)$“的根据。

4. LeetCode 3：无重复字符的最长子串

题目：给定字符串 s，求其中无重复字符的最长子串的长度。

套路：可变窗口、求最长。约束是"窗口内字符全部不同”。当 s[right] 已经在窗口里时，把 left 直接跳到上一次出现位置的下一格。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
def length_of_longest_substring(s):
    """LeetCode 3：无重复字符的最长子串。"""
    last_seen = {}        # 字符 -> 最近一次出现的下标
    left = 0
    best = 0

    for right, ch in enumerate(s):
        if ch in last_seen and last_seen[ch] >= left:
            # 跳过上一次出现位置，O(1) 完成收缩
            left = last_seen[ch] + 1
        last_seen[ch] = right
        best = max(best, right - left + 1)

    return best

Java 版本

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
public int lengthOfLongestSubstring(String s) {
    Map<Character, Integer> lastSeen = new HashMap<>();
    int left = 0, best = 0;
    for (int right = 0; right < s.length(); right++) {
        char c = s.charAt(right);
        if (lastSeen.containsKey(c) && lastSeen.get(c) >= left) {
            left = lastSeen.get(c) + 1;
        }
        lastSeen.put(c, right);
        best = Math.max(best, right - left + 1);
    }
    return best;
}

复杂度：时间 $O(n)$，每个字符最多被插入和移出哈希表各一次；空间 $O(\min(n, |\Sigma|))$，$|\Sigma|$ 是字符集大小。

两种写法：上面这版是"跳跃式收缩"——left 一步跳过去；另一种"步进式收缩"是用频次表配 while count[s[right]] > 1: drop(s[left]); left += 1。两者都是 $O(n)$，跳跃版代码短，步进版的好处是更容易扩展到"最多包含 k 种字符"那类变体。

5. LeetCode 76：最小覆盖子串

题目：给定字符串 s 和 t，返回 s 中能覆盖 t 所有字符（含重数）的最短子串；不存在则返回 ""。

套路：可变窗口、求最短。约束是"窗口内每个目标字符的出现次数都达标"。先扩到合法，再尽力收缩。

判断窗口是否合法时，最干净的办法是维护一个 valid 计数器：表示当前有多少种目标字符的出现次数已经"达标"。当 valid == len(need) 时整个窗口就合法了，避免了每一步都比对两个哈希表。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
from collections import Counter

def min_window(s, t):
    """LeetCode 76：覆盖 t 所有字符的最短子串。"""
    if not s or not t or len(s) < len(t):
        return ""

    need = Counter(t)
    have = {}
    valid = 0                     # 已达标的字符种类数
    left = 0
    best_len = float("inf")
    best_start = 0

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

        # 窗口合法时尝试收缩
        while valid == len(need):
            if right - left + 1 < best_len:
                best_len = right - left + 1
                best_start = left

            drop = s[left]
            left += 1
            if drop in need:
                if have[drop] == need[drop]:
                    valid -= 1            # 收缩之后即将失衡
                have[drop] -= 1

    return "" if best_len == float("inf") else s[best_start:best_start + best_len]

Java 版本

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public String minWindow(String s, String t) {
    if (s.length() < t.length()) return "";
    Map<Character, Integer> need = new HashMap<>();
    for (char c : t.toCharArray()) need.merge(c, 1, Integer::sum);

    Map<Character, Integer> have = new HashMap<>();
    int valid = 0, left = 0;
    int bestLen = Integer.MAX_VALUE, bestStart = 0;

    for (int right = 0; right < s.length(); right++) {
        char c = s.charAt(right);
        if (need.containsKey(c)) {
            have.merge(c, 1, Integer::sum);
            if (have.get(c).intValue() == need.get(c).intValue()) valid++;
        }
        while (valid == need.size()) {
            if (right - left + 1 < bestLen) {
                bestLen = right - left + 1;
                bestStart = left;
            }
            char d = s.charAt(left++);
            if (need.containsKey(d)) {
                if (have.get(d).intValue() == need.get(d).intValue()) valid--;
                have.merge(d, -1, Integer::sum);
            }
        }
    }
    return bestLen == Integer.MAX_VALUE ? "" : s.substring(bestStart, bestStart + bestLen);
}

复杂度：时间 $O(|s| + |t|)$，两个指针都是单调推进；空间 $O(|\Sigma|)$。

容易写错的地方是这一行：if have[drop] == need[drop]: valid -= 1。我们要在 have 真的减下去之前判断"现在恰好达标，移走一个就要失衡了"，所以判断必须在自减之前。顺序写反，valid 就会跟实际窗口对不上。

6. LeetCode 567：字符串的排列

题目：判断 s2 中是否存在某个子串是 s1 的一个排列。

套路：长度为 len(s1) 的固定窗口。两个字符串互为排列当且仅当字符频率向量相同，所以只要在 s2 上维护一个长度 26 的频率数组，跟 s1 的频率数组比较就行。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
def check_inclusion(s1, s2):
    """LeetCode 567：s2 是否包含 s1 的某个排列？"""
    n, m = len(s1), len(s2)
    if n > m:
        return False

    need = [0] * 26
    have = [0] * 26
    for c in s1:
        need[ord(c) - ord('a')] += 1
    for c in s2[:n]:
        have[ord(c) - ord('a')] += 1

    # 当前 26 个桶里有几个对得上
    matches = sum(1 for i in range(26) if need[i] == have[i])

    for right in range(n, m):
        if matches == 26:
            return True

        r = ord(s2[right]) - ord('a')
        l = ord(s2[right - n]) - ord('a')

        # 右边新元素进入
        have[r] += 1
        if have[r] == need[r]:
            matches += 1
        elif have[r] == need[r] + 1:
            matches -= 1

        # 左边旧元素离开
        have[l] -= 1
        if have[l] == need[l]:
            matches += 1
        elif have[l] == need[l] - 1:
            matches -= 1

    return matches == 26

Java 版本

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public boolean checkInclusion(String s1, String s2) {
    int n = s1.length(), m = s2.length();
    if (n > m) return false;
    int[] need = new int[26], have = new int[26];
    for (int i = 0; i < n; i++) {
        need[s1.charAt(i) - 'a']++;
        have[s2.charAt(i) - 'a']++;
    }
    int matches = 0;
    for (int i = 0; i < 26; i++) if (need[i] == have[i]) matches++;
    for (int right = n; right < m; right++) {
        if (matches == 26) return true;
        int r = s2.charAt(right) - 'a';
        int l = s2.charAt(right - n) - 'a';
        have[r]++;
        if (have[r] == need[r]) matches++;
        else if (have[r] == need[r] + 1) matches--;
        have[l]--;
        if (have[l] == need[l]) matches++;
        else if (have[l] == need[l] - 1) matches--;
    }
    return matches == 26;
}

复杂度：时间 $O(m)$，靠 matches 计数器把"比较两个频率数组"的 $O(26)$ 也省掉了；空间 $O(1)$。

**LeetCode 438（找到所有字母异位词）**完全可以套这个模板，只是把"提前返回"换成"收集起始下标"。

7. 进阶变体：滑动窗口最大值（单调队列）

当窗口要查询的不是和、不是计数，而是窗口内的最大值或最小值时，简单的"加一个、减一个"就不够用了——因为移除当前最大值后，下一个最大值在哪里我们并不知道。这时的标准做法是单调队列：队列里的元素按值严格递减，队首始终是当前窗口的最大值。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
from collections import deque

def max_sliding_window(nums, k):
    """LeetCode 239：每个长度为 k 的窗口的最大值。"""
    dq = deque()      # 存下标；对应的值在 nums 上严格递减
    out = []

    for i, x in enumerate(nums):
        # 1. 把队尾比 x 小的全部踢掉——它们不可能再当最大值了
        while dq and nums[dq[-1]] < x:
            dq.pop()
        dq.append(i)

        # 2. 队首如果已经滑出窗口，弹掉
        if dq[0] <= i - k:
            dq.popleft()

        # 3. 窗口够大时，队首就是答案
        if i >= k - 1:
            out.append(nums[dq[0]])

    return out

每个下标至多入队、出队各一次，整体仍是 $O(n)$。

8. 什么时候用滑动窗口

下面这棵决策树总结了"什么形状的问题该用滑动窗口的哪种姿势"：

满足下列三条时，优先考虑滑动窗口：

答案是某段连续区间（子数组、子串）。
区间属性可以增量维护——窗口移动一格只需做常数次操作（如累加和、计数表、单调队列）。
目标要么是固定大小（k），要么是最长 / 最短的合法区间。

如果不连续、需要全局信息、或者要任意撤销操作，那就别强行套滑动窗口，换前缀和、双指针、动态规划或堆才是正解。

9. 三套值得背下来的模板

固定窗口

1
2
3
4
5
6
7
8
def fixed_window(arr, k):
    state = init_state(arr[:k])           # 例如和、频次表
    best = report(state)
    for right in range(k, len(arr)):
        state = add(state, arr[right])
        state = remove(state, arr[right - k])
        best = better(best, report(state))
    return best

可变窗口——求最长合法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
def longest_valid(arr):
    left = 0
    state = empty_state()
    best = 0
    for right, x in enumerate(arr):
        state = add(state, x)
        while not is_valid(state):
            state = remove(state, arr[left])
            left += 1
        best = max(best, right - left + 1)
    return best

可变窗口——求最短合法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
def shortest_valid(arr):
    left = 0
    state = empty_state()
    best = float("inf")
    for right, x in enumerate(arr):
        state = add(state, x)
        while is_valid(state):
            best = min(best, right - left + 1)
            state = remove(state, arr[left])
            left += 1
    return best if best != float("inf") else 0

10. 常见陷阱

窗口长度差一：长度是 right - left + 1，不是 right - left。
valid 更新时机搞反：have[c] 首次等于 need[c] 时 valid += 1；即将跌破时 valid -= 1。先减计数还是先判断，差一步计数器就乱了。
用 list.pop(0) 维护固定窗口：那是 $O(k)$ 的操作。请用 collections.deque 或者直接靠下标，保持 $O(1)$。
每次都重新计算窗口：滑动窗口的全部价值就在于增量更新；只要内层还在扫整个窗口，渐进复杂度就退回去了。
“和 ≥ target” 遇到负数：收缩时和不一定下降，“求最短"模板会失效。这时考虑前缀和 + 单调队列，或者换思路。

11. 推荐练习题清单

难度	题号与名称	适用模板
简单	LC 643 子数组最大平均数 I	固定窗口
简单	LC 1456 定长子串中元音的最大数目	固定窗口
中等	LC 3 无重复字符的最长子串	求最长
中等	LC 159 / 340 至多包含 K 个不同字符的最长子串	求最长
中等	LC 209 长度最小的子数组	求最短
中等	LC 424 替换后的最长重复字符	求最长
中等	LC 567 字符串的排列	固定窗口
中等	LC 438 找到字符串中所有字母异位词	固定窗口
中等	LC 713 乘积小于 K 的子数组	求最长
中等	LC 1004 最大连续 1 的个数 III	求最长
困难	LC 76 最小覆盖子串	求最短
困难	LC 239 滑动窗口最大值	单调队列
困难	LC 30 串联所有单词的子串	固定窗口 + 哈希

12. 总结

滑动窗口的本质是一个摊还分析：与其每个窗口都从头算一遍，不如维护一小块状态，让它随着边界推进做增量更新。两个指针都单调右移，于是把暴力的 $O(n^2)$ 压到 $O(n)$。

碰到连续区间题时，给自己问四个问题：

窗口大小是固定还是可变？
如果可变，是求最长合法窗口，还是最短合法窗口？
我要维护什么状态——和、频次表，还是单调队列？
什么是窗口的不变量，谁的移动会破坏它？

这四个问题想清楚了，绝大多数滑动窗口题就只剩下"往模板里填空"的工作。

1. 一图看懂滑动窗口

2. 固定窗口：大小为 k 的最大子数组和

3. 可变窗口的两种姿势

4. LeetCode 3：无重复字符的最长子串

5. LeetCode 76：最小覆盖子串

6. LeetCode 567：字符串的排列

7. 进阶变体：滑动窗口最大值（单调队列）

8. 什么时候用滑动窗口

9. 三套值得背下来的模板

10. 常见陷阱

11. 推荐练习题清单

12. 总结

Liked this piece?