滑动窗口

2026-06-02

两个指针 l、r,r 一路往右扩;窗口”违法”了就 l 往右收,合法了就更新答案。两个指针各自最多走 N 步, 砸穿 的暴力枚举。

直觉 — 两指针单调推进

把暴力枚举所有子数组想象成一个二维网格 , 个格子。滑动窗口只走其中一条单调路径: r 永远只增,l 也永远只增。两个指针加起来最多 步,所以 。

为什么 l 不会回退? 因为 r 往右一步只会让窗口”更违法”(更多元素、更大和、更多重复),已经退到合法的 l 没有理由再往左跑回去 — 那只会让窗口又变违法。

什么时候能用滑动窗口

关键判定: 单调性。 必须满足:

  • 窗口扩大 → 条件朝一个方向变化(更违法 / 更合法)
  • 窗口缩小 → 朝相反方向变化

比如”子数组和 target”: 加元素和只增,减元素和只减,合法性单调,能滑。比如”恰好 K 个不同字符”: 扩张/收缩都可能让”恰好 K”失败,没有单调性,不能直接滑(转化成”至多 K - 至多 K-1”,见下文)。

判错就死: 看到题先问一句”扩大窗口,条件是不是只朝一个方向走?”是,才能滑。

动画 — 两种模板并排看

下面动画分两部分。上半演示「最长无重复子串」("abcabcbb"),看 r 扩到出现重复时 l 怎么收,ans 在 while 循环外更新。下半左右对比同一套指针逻辑下两种 ans 更新位置: 左边「最长合法」(while 违法时收,while 外更新),右边「最短覆盖」(while 合法时记录,while 内更新)。

重点看两件事: (1) l 从来不回退;(2) ans 更新的位置决定了你算的是最长还是最短。

两种模板 — 最长合法 vs 最短覆盖

模板 A: 最长合法窗口(while 违法时收)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def longest_valid(s):
    from collections import Counter
    window = Counter()
    left = 0
    ans = 0
    for right, c in enumerate(s):
        window[c] += 1                 # r 进窗口
        while not_valid(window):       # 违法就收
            window[s[left]] -= 1
            if window[s[left]] == 0:
                del window[s[left]]
            left += 1
        ans = max(ans, right - left + 1)  # while 外更新 (此时一定合法)
    return ans

直觉: 出 while 时窗口刚刚回到合法,这是以 right 为右端的最大合法窗口,记下来。

模板 B: 最短覆盖窗口(while 合法时记)

1
2
3
4
5
6
7
8
9
10
11
12
13
def shortest_cover(s, t):
    from collections import Counter
    need = Counter(t)
    window = Counter()
    left = 0
    ans = float('inf')
    for right, c in enumerate(s):
        window[c] += 1                 # r 进窗口
        while is_valid(window, need):  # 合法就一直缩
            ans = min(ans, right - left + 1)  # while 内更新
            window[s[left]] -= 1
            left += 1
    return ans

直觉: 进 while 说明已经合法,在收缩过程中每一步都是一个合法窗口,贪心地取最短。一旦 l 收到再收就违法,跳出去等 r 继续扩。

怎么对应到题目

题目特征 用哪个模板 ans 更新位置
找最长 X 子数组 A: 最长合法 while 外
找最短 X 子数组 B: 最短覆盖 while 内
数有多少子数组 X A 的变体: ans += right - left + 1 while 外

第三种是高频小变招: 出 while 后 [left..right] 是以 right 结尾的最大合法窗口,所以以 right 结尾的合法子数组共有 right - left + 1 个。

经典题速过

LC 3. 无重复字符的最长子串 (模板 A)

1
2
3
4
5
6
7
8
9
10
def lengthOfLongestSubstring(s):
    window = {}
    left = ans = 0
    for right, c in enumerate(s):
        window[c] = window.get(c, 0) + 1
        while window[c] > 1:           # 重复才违法,只可能是新进来的 c
            window[s[left]] -= 1
            left += 1
        ans = max(ans, right - left + 1)
    return ans

小优化: 违法当且仅当新进来的 c 重复,所以 while window[c] > 1 比扫整个 window 快。

LC 209. 长度最小的子数组 (模板 B)

1
2
3
4
5
6
7
8
9
10
def minSubArrayLen(target, nums):
    left = total = 0
    ans = float('inf')
    for right, x in enumerate(nums):
        total += x
        while total >= target:          # 合法
            ans = min(ans, right - left + 1)
            total -= nums[left]
            left += 1
    return ans if ans < float('inf') else 0

LC 76. 最小覆盖子串 (模板 B + 计数器)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def minWindow(s, t):
    from collections import Counter
    need = Counter(t)
    window = Counter()
    have = 0                            # 已满足的字符种类数
    required = len(need)
    left = 0
    ans = (float('inf'), 0, 0)
    for right, c in enumerate(s):
        window[c] += 1
        if c in need and window[c] == need[c]:
            have += 1
        while have == required:         # 合法
            if right - left + 1 < ans[0]:
                ans = (right - left + 1, left, right)
            window[s[left]] -= 1
            if s[left] in need and window[s[left]] < need[s[left]]:
                have -= 1
            left += 1
    return s[ans[1]:ans[2]+1] if ans[0] < float('inf') else ""

关键: 用 have 记录”已满足字符种类数”,避免每次扫整个 Counter 判合法,这样合法性判断真的是 。

“恰好 K” = “至多 K” - “至多 K-1” (LC 992)

恰好 K 没单调性 → 转成两个有单调性的”至多”:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def exactly_k(nums, k):
    return at_most(nums, k) - at_most(nums, k - 1)

def at_most(nums, k):
    from collections import Counter
    cnt = Counter()
    left = ans = 0
    for right, x in enumerate(nums):
        cnt[x] += 1
        while len(cnt) > k:
            cnt[nums[left]] -= 1
            if cnt[nums[left]] == 0:
                del cnt[nums[left]]
            left += 1
        ans += right - left + 1         # 以 right 结尾的合法子数组数
    return ans

不写错的三条铁律

  • 进出对称: right 进窗口做的操作,left 出窗口做对应逆操作。Counter 别忘了在归零时 del,否则 len(cnt) 不对。
  • left 只在 while 里动: 在外面动 left,均摊分析直接崩。
  • ans 位置 = 题目意图: while 外 → 最长 / 计数;while 内 → 最短。

记忆法

一句话: r 扩到违法 → l 缩到合法。

判断三连问:

  1. 扩窗朝一个方向变(单调)? 不是 → 不能滑(或转化)。
  2. 找最长还是最短? 最长 → while 违法时收,while 外更新;最短 → while 合法时记,while 内更新。
  3. 进出对称写好了吗? Counter 归零删,sum 加完减。

看到”连续子数组/子串 + 最长/最短/计数”,条件反射写两指针外加一个 while。错不了。

思考题

为什么左指针只向右移动,不会回退? 这保证了什么复杂度?

r 右移后窗口只可能”更违法”,已经退到合法的 l 没理由再往左走 — 那只会让窗口又变违法。左右指针各自最多走 步,总操作 。这是均摊分析的经典例子: 看似 for + while 两层 ,实际上 while 总执行次数被 l 的总位移上限锁死。

"恰好 K 个不同字符" 为什么不能直接滑窗? 怎么转化?

恰好 K 时,扩张可能跳到 K+1(违法),收缩可能跳到 K-1(也违法),两个方向都没单调性,while 循环没法维护。

转化: 恰好 K = 至多 K - 至多 (K-1)。”至多 K” 有单调性(窗口越大越可能超 K),可以标准滑窗。

模板 A 里,为什么 `ans` 必须在 while 外更新?

while 里窗口正在”从违法收回合法”的过程中,中间状态都是违法的。出 while 才保证 [left..right] 是当前合法窗口,而且是以 right 为右端能达到的最大合法窗口。在违法时更新 ans 会污染答案。

LeetCode 练习

热身:

进阶: