不定长滑动窗口：面试完全指南

概述

这是滑动窗口系列的第二篇。如果你还没读过第一篇，建议先阅读定长滑动窗口。

不定长滑动窗口（又称双指针）是编程面试中最常考的模式之一。与定长窗口不同，窗口会根据特定条件动态地扩展和收缩。

---

定长 vs 不定长

方面	定长窗口	不定长窗口
窗口大小	固定为 k	动态变化
指针数量	一个指针 (i)	两个指针 (left, right)
收缩条件	每次固定收缩 1	满足条件时持续收缩
适用场景	”每个大小为 k 的窗口"	"满足…的最长/最短子数组”

定长窗口 (大小 k=3):
[a b c] d e f → a [b c d] e f → a b [c d e] f → a b c [d e f]
  ↑                ↑                ↑                ↑
  始终保持大小为 3

不定长窗口:
[a] b c d → [a b] c d → [a b c] d → a [b c] d → a [b c d]
↑           ↑           ↑           ↑           ↑
根据合法性动态扩展和收缩

---

两种核心模式

不定长滑动窗口问题分为两类：

模式1：找最长合法子数组

• 目标： 在保持窗口合法的前提下最大化窗口
• 逻辑： 右指针扩展，不合法时左指针收缩
• 更新： 收缩之后（窗口刚刚变得合法）

模式2：找最短合法子数组

• 目标： 在保持窗口合法的前提下最小化窗口
• 逻辑： 右指针扩展直到合法，然后尽可能收缩
• 更新： 在 while 循环内（窗口仍然合法）

---

题目1：最多连续1的个数 II (LC 487)

题目： 给定一个二进制数组 nums，如果最多可以翻转一个 0，返回数组中连续 1 的最大个数。

示例：

• 输入：nums = [1, 0, 1, 1, 0]
• 输出：4
• 解释：翻转第一个零得到 [1, 1, 1, 1, 0]，有 4 个连续的 1。

解题思路

这是一个**“找最长”问题。我们维护一个最多包含一个零**的窗口。

nums = [1, 0, 1, 1, 0]

第1步: [1]           → 0 个零, 合法, 长度=1
第2步: [1, 0]        → 1 个零, 合法, 长度=2
第3步: [1, 0, 1]     → 1 个零, 合法, 长度=3
第4步: [1, 0, 1, 1]  → 1 个零, 合法, 长度=4 ✓
第5步: [1, 0, 1, 1, 0] → 2 个零, 不合法!
       收缩: [0, 1, 1, 0] → 仍有 2 个零
       收缩: [1, 1, 0] → 1 个零, 合法, 长度=3
        
结果: 4

交互式可视化

观察窗口如何通过 right 指针扩展，以及当零的数量超过限制时如何通过 left 指针收缩：

关键观察：

• 绿色 (1)： 窗口中的有效元素
• 红色 (0)： 我们正在”翻转”的零 - 最多允许 k 个
• L 指针： 当窗口不合法时收缩
• R 指针： 始终向右扩展探索新元素

JavaPythonJavaScript

Loading...

复杂度：

• 时间： O(n) - 每个元素最多被访问两次（一次被 right，一次被 left）
• 空间： O(1) - 只使用了几个整数变量，与输入大小无关

---

题目2：最小覆盖子串 (LC 76)

题目： 给你一个字符串 s 和一个字符串 t，返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 ""。

这是一道经典的**“找最短”**问题，也是面试官的最爱。

示例：

• 输入：s = "ADOBECODEBANC", t = "ABC"
• 输出："BANC"
• 解释：包含 A, B, C 的最小窗口是 “BANC”。

解题思路

使用两个哈希表：

1. need：需要从 t 中获取的每个字符的计数
2. window：当前窗口中每个字符的计数

用 valid 跟踪满足条件的字符数。

s = "ADOBECODEBANC", t = "ABC"

扩展直到合法（包含 A, B, C）:
[ADOBEC] → 合法! 长度=6, 记录
收缩直到不合法:
[DOBEC] → 缺少 A, 停止

继续扩展...
[DOBECODEBA] → 合法!
[OBECODEBA] → 合法! 长度=9
[BECODEBA] → 合法! 长度=8
[ECODEBA] → 缺少 C, 停止

...最终...
[BANC] → 合法! 长度=4 ✓

最小窗口可视化

观察算法如何找到最小窗口。注意关键区别：我们在 while 循环内部更新结果，即窗口合法时更新，然后收缩以寻找更小的合法窗口。

关键观察：

• Need： 目标字符串 t 中需要的字符
• Window： 当前窗口中的字符计数
• 结果在收缩时更新（在 while 循环内部）
• 持续收缩直到窗口变得不合法

朴素解法：Map 比较（O(|Σ| × m + n)）

JavaPythonJavaScript

Loading...

复杂度： 时间 O(|Σ| × m + n)，空间 O(|Σ|) —— 每次 included() 都扫描 t 的全部键。

---

基础解法：valid 计数器（O(m + n)）

JavaPythonJavaScript

Loading...

为什么是 O(m + n)?

• 每个字符最多被加入/移除一次
• valid == need.size() 是 O(1)，因为我们只更新被触碰的字符
• 总复杂度：外层 O(m) + 初始化 O(n)

---

优化解法：单计数数组（O(m + n)）

这种方法使用单个计数数组和一个 less 变量。它与基础解法具有相同的 O(m + n) 复杂度，但代码更简洁，常数因子略小。

核心思想：将两个 Map 合并为一个

不再分别维护 need 和 window 两个 map，我们使用：

cnt[c] = (t 中需要的字符数) - (窗口中已有的字符数)
       = need[c] - window[c]

cnt[c] 告诉我们什么？

cnt[c] 的值	含义
> 0	窗口中字符 c 不足
= 0	窗口中字符 c 刚好满足
< 0	窗口中字符 c 有多余

less 变量

less = cnt[c] > 0 的字符种类数（即不足的字符种类数）

当 less == 0 时：每种字符都有 cnt[c] ≤ 0，意味着窗口覆盖了所有需要的字符！

逐步示例

s = "ADOBEC", t = "ABC"
初始: cnt = {A:1, B:1, C:1}, less = 3

第1步: 加入 'A'
  cnt[A]-- → cnt = {A:0, B:1, C:1}
  cnt[A] == 0? 是! less-- → less = 2
  less == 0? 否, 继续扩展

第2步: 加入 'D'
  cnt[D]-- → cnt = {A:0, B:1, C:1, D:-1}
  cnt[D] == 0? 否 (是 -1)
  less == 0? 否, 继续扩展

第3步: 加入 'O'
  cnt[O]-- → cnt = {..., O:-1}
  less == 0? 否, 继续扩展

第4步: 加入 'B'
  cnt[B]-- → cnt = {A:0, B:0, C:1, ...}
  cnt[B] == 0? 是! less-- → less = 1
  less == 0? 否, 继续扩展

第5步: 加入 'E'
  cnt[E]-- → cnt = {..., E:-1}
  less == 0? 否, 继续扩展

第6步: 加入 'C'
  cnt[C]-- → cnt = {A:0, B:0, C:0, ...}
  cnt[C] == 0? 是! less-- → less = 0
  less == 0? 是! 窗口 "ADOBEC" 合法!
  
  现在收缩:
    移除 'A': cnt[A] 原来是 0, 所以 less++ → less = 1
    窗口不合法, 停止收缩

为什么合法性检查是 O(1)？

// 将字符 c 加入窗口:
cnt[c]--;
if (cnt[c] == 0) less--;  // O(1) 检查, O(1) 更新

// 将字符 x 从窗口移除:
if (cnt[x] == 0) less++;  // O(1) 检查, O(1) 更新
cnt[x]++;

// 合法性检查:
while (less == 0) { ... }  // O(1) 检查!

每个操作都是 O(1)，所以总复杂度是 O(m + n)。

JavaPythonJavaScript

Loading...

复杂度（与基础解法相同）：

• 时间： O(m + n) - 每个字符最多被访问两次（一次被 right，一次被 left），所有操作都是 O(1)
• 空间： O(|Σ|)，其中 |Σ| = 128（ASCII 字符）或 52（仅字母）

为什么使用这种方法？

1. 代码更简洁： 一个数组代替两个 map
2. 略微更快： 数组访问比 HashMap 更快
3. 更易理解： less 变量直接回答”是否完成？“

常见错误

1. 忘记处理重复字符： 如果 t = "AAB"，你需要 2 个 A，而不是 1 个
2. 比较方式错误： Java 中对 Integer 对象使用 .equals()
3. 边界错误： 窗口长度是 right - left + 1

---

题目3：可获得的最大点数 (LC 1423)

题目： 几张卡牌排成一行，每张卡牌都有一个对应的点数。给你整数数组 cardPoints 和整数 k，每次行动可以从首端或末端取一张卡牌，共取 k 张。返回可以获得的最大点数。

示例：

• 输入：cardPoints = [1, 2, 3, 4, 5, 6, 1], k = 3
• 输出：12
• 解释：从右边取三张卡牌：5 + 6 + 1 = 12。

解题思路

这道题看起来需要动态规划，但有一个巧妙的滑动窗口技巧！

关键洞察： 如果我们从两端取 k 张牌，我们会在中间留下一个大小为 n-k 的连续子数组。

cardPoints = [1, 2, 3, 4, 5, 6, 1], k = 3
n = 7, 窗口大小 = n - k = 4

总和 = 22

找大小为 4 的最小窗口和:
[1, 2, 3, 4] = 10
[2, 3, 4, 5] = 14
[3, 4, 5, 6] = 18
[4, 5, 6, 1] = 16

最小值 = 10
答案 = 22 - 10 = 12 ✓

这就转化成了一个定长滑动窗口问题！

JavaPythonJavaScript

Loading...

复杂度：

• 时间： O(n) - 计算初始窗口和并滑动遍历数组一次
• 空间： O(1) - 只使用了几个整数变量，与输入大小无关

---

题目4：统计最大值至少 K 次的子数组 (LC 2962)

题目： 给定数组 nums，统计其中全局最大值出现至少 k 次的子数组个数。

示例：

• 输入：nums = [1,3,2,3,3], k = 2
• 全局最大值 = 3
• 合法子数组数量 = 6

解题思路（滑动窗口 + 贡献共享）

1. 预处理 maxVal = max(nums)
2. 双指针滑窗，维护窗口内 maxVal 出现次数 cntMax
3. 对每个 right：
   • 加入 nums[right]，若等于 maxVal 则 cntMax++
   • 当 cntMax >= k 时，不断右移 left（移出 maxVal 时 cntMax--）
   • while 结束后，left 是“刚好不合法”的起点
   • 贡献： 对当前 right，所有起点 0..left-1 都合法，因此答案加 left

为什么 ans += left（共享思想）？

• 窗口第一次满足条件时，left 之前的所有起点对当前 right 都是合法的。
• 当 right 继续右移，这些起点仍然有效，直到 left 移过一个 maxVal。
• 所以每个 right 只需累加当前合法起点的个数（left）。

伪代码

maxVal = max(nums)
cntMax = 0; left = 0; ans = 0
for right in 0..n-1:
    if nums[right] == maxVal: cntMax++
    while cntMax >= k:
        if nums[left] == maxVal: cntMax--
        left++
    ans += left   # 当前 right 的合法起点个数
return ans

复杂度： 时间 O(n)，空间 O(1)。

参考： LC 2962 题解

---

模板与套路

模板1：找最长合法子数组

JavaPythonJavaScript

Loading...

适用于： 无重复字符的最长子串、最多包含 K 个不同元素的最长子数组等。

模板2：找最短合法子数组

JavaPythonJavaScript

Loading...

适用于： 最小覆盖子串、长度最小的子数组等。

---

使用场景

✅ 使用不定长滑动窗口当：

• 寻找最长/最短子数组/子串
• 题目提到**“连续”或”相邻”**
• 条件涉及最多/至少 K 个某元素
• 需要找满足条件的最小/最大子数组

❌ 不使用当：

• 元素可以不连续
• 顺序不重要（考虑排序）
• 需要考虑所有可能组合（DP 可能更好）

相关模式

问题类型	模式
固定窗口大小	定长滑动窗口
动态窗口大小	不定长滑动窗口（本文）
有序数组求和	双指针（相向移动）
链表环检测	快慢指针

---

复杂度分析

为什么是 O(n)？

总操作数 = right 的移动次数 + left 的移动次数
        = n + (最多 n)
        = O(2n)
        = O(n)

关键洞察：left 只会递增，不会递减。所以整个算法中，left 最多移动 n 次。

---

总结

方面	最长模式	最短模式
目标	最大化窗口	最小化窗口
收缩条件	窗口不合法时	窗口合法时
更新结果	while 循环之后	while 循环内部
例题	LC 487, LC 3	LC 76, LC 209

核心要点：

1. 不定长窗口使用两个指针（left, right）
2. 区分”找最长”和”找最短”两种模式
3. 在正确的位置更新结果
4. 时间复杂度是 O(n)，不是 O(n²)