不定长滑动窗口（求最短）
与"求最长"对偶——把 update-ans 搬进 while 内部，统一拿下 LC 209 / 76 / 862
1. 核心原理：从"求最长"到"求最短"
上一节给出了"不定长滑窗求最长"的三段式模板：in → while not_satisfied: shrink → update-ans。本节的形态看起来只是把题面里的"最长"换成"最短"，但模板里有一个致命的小改动——错了你会得到全 0 的 WA 或永不收缩的 TLE。
"给定数组/字符串，求满足某个条件的最短连续子区间长度。"
典型题目：LC 209（和 ≥ target 的最短子数组）、LC 76（覆盖 t 所有字符的最短子串）、LC 1234（替换后平衡的最短子串）。这些题的共同结构是：条件是"达到某个下界"，越往右扩越容易满足，但我们要的是刚刚好满足的瞬间。
模板的关键差异
求最长把 ans = max(ans, r - l + 1) 写在 while 退出之后；求最短把 ans = min(ans, r - l + 1) 写在 while 内部，每收缩一步都试更新。这是本节唯一也是最重要的差异点。
为什么？拿一对反义场景对比：
- 求最长：窗口越大越好。等到 while 不能再扩张（条件被破坏）时窗口"刚好不合法"，回退一步就是最长合法候选——这是上一节的逻辑（注意本节不是这个）。
- 求最短：窗口越小越好。每当窗口"恰好满足条件"那一刻就是局部最优。一旦满足，进入 while shrink；每次 shrink 一步，先更新 ans 再让 l 前进——因为 l 再往前迈一步，条件可能就被破坏了，那时再更新就来不及了。
一句话总结："求最长在'踩刹车'前一刻拍照、求最短在'踩刹车'过程中每一步都拍照"。
北美面试切入点
LC 209 是"求最短子数组和 ≥ K"——难度不高，用来确认能不能正确写出滑窗的过滤器题。真正难一档的是 LC 76 Minimum Window Substring，在 Meta tag 里属于经常出现的中等偏难题。LC 862（含负数的最短子数组和）则常用来考察"何时滑窗失效、要换成前缀和 + 单调队列"——是 Big Tech 算法面试里典型的进阶题。
把本节模板吃透，等于拿到了"求最短"系列题目的通行证。
2. 通用模板对比
两段并排伪代码，把求最长与求最短的差异钉死：
# 求最长 (Round 2 / 上一节)
l, ans = 0, 0
for r, x in enumerate(arr):
add(x)
while not_satisfied(): # 破坏时收缩
remove(arr[l]); l += 1
ans = max(ans, r - l + 1) # while 外更新
# 求最短 (本节)
l, ans = 0, INF
for r, x in enumerate(arr):
add(x)
while satisfied(): # 满足时收缩 (反过来!)
ans = min(ans, r - l + 1) # while 内更新 (先更新再 shrink)
remove(arr[l]); l += 1
return ans if ans < INF else 0 # 兜底: 无解返回 0三个必须记住的区别
- while 条件反过来：求最长是
not_satisfied()（破坏时收缩），求最短是satisfied()（满足时收缩）。写反了直接死循环或全错。 - ans 初值是
INF：因为要取 min，初值必须比任何合法答案大；最终若ans == INF表示从未进入过 while，即整个数组都凑不出合法窗口，需要兜底返回 0（或题目要求的特殊值）。 - update-ans 搬进 while 内部：每收缩一步都试一次
min。这是因为 shrink 的下一步可能就让条件不再满足、退出 while——错过这一步就再没机会更新这个右端点对应的最优解。
3. ASCII 图解
以 LC 209 在 nums = [2, 3, 1, 2, 4, 3]、target = 7 上为例。cur_sum 跟踪窗口和，r 每步前进 1，l 仅在 cur_sum >= 7 时连续收缩，每步都试更新 ans：
Step 1: [2] 3 1 2 4 3 cur_sum=2, ans=INF
l (in: +2)
r
Step 2: [2 3] 1 2 4 3 cur_sum=5, ans=INF
l r (in: +3)
Step 3: [2 3 1] 2 4 3 cur_sum=6, ans=INF
l r (in: +1)
Step 4: 满足: cur_sum=8>=7, 进入 while shrink
[2 3 1 2] 4 3 cur_sum=8, ans=4
l r (in: +2, update ans=min(INF,4)=4)
先 update 再 shrink:
2 [3 1 2] 4 3 cur_sum=6, ans=4 (退出 while)
l r (out: -2)
Step 5: 不满足: cur_sum=6<7, 跳过 while, 继续扩张
2 [3 1 2 4] 3 cur_sum=10, ans=4
l r (in: +4)
Step 6: 满足: cur_sum=10>=7, 连续 shrink
2 [3 1 2 4] 3 update ans=min(4,4)=4
l r
2 3 [1 2 4] 3 cur_sum=7, update ans=min(4,3)=3
l r (out: -3)
2 3 1 [2 4] 3 cur_sum=6, 退出 while (不再满足)
l r (out: -1)
Step 7: 不满足, 扩张
2 3 1 [2 4 3] cur_sum=9, ans=3
l r (in: +3)
Step 8: 满足: 再次 shrink
2 3 1 [2 4 3] update ans=min(3,3)=3
l r
2 3 1 2 [4 3] cur_sum=7, update ans=min(3,2)=2 ← 最优!
l r (out: -2)
2 3 1 2 4 [3] cur_sum=3, 退出 while (不再满足)
l
r (out: -4)
最终 ans = 2 → 子数组 [4, 3]注意三个关键现象：
- Step 4 与 Step 6：一旦满足
cur_sum >= 7，立刻进入 while。先 update ans 再 shrink——shrink 一步可能就让条件破坏。 - Step 6 → Step 8：右指针每前进一步只发生一次 while 循环，但 while 内部可以收缩多次。每一次收缩都是一个"更短的合法窗口候选"。
- Step 8 是全局最优：
[4, 3]长度 2。它发生在 r=5、l=4 的瞬间，窗口和恰好 = 7，再 shrink 一步就破坏条件。这正是"求最短"的本质——在合法的最后一刻拍照。
不定长滑动窗口（求最短）
LeetCode 209 · 长度最小的子数组
4. 母题精讲
LeetCode 209. Minimum Size Subarray Sum
题目（中文翻译）：给定一个正整数数组 nums 和一个正整数 target，找出 nums 中总和大于等于 target 的最短连续子数组的长度。若不存在这样的子数组，返回 0。
样例 1：
输入: target = 7, nums = [2, 3, 1, 2, 4, 3]
输出: 2
解释: 子数组 [4, 3] 满足 4+3=7>=7, 且是最短的.样例 2：
输入: target = 11, nums = [1, 1, 1, 1, 1]
输出: 0
解释: 总和只有 5, 不存在满足条件的子数组.思路推导
为什么滑窗适用？ 关键性质：nums 全是正整数，所以 cur_sum 关于窗口长度单调递增。这意味着：
- 右指针 r 前进 →
cur_sum增加 → 更容易满足>= target - 左指针 l 前进 →
cur_sum减少 → 更难满足>= target
单调性是滑窗的命根子。一旦 nums 含负数（如 LC 862），左指针前进时 cur_sum 可能反而变大，这条性质就被破坏，朴素滑窗失效——这正是 LC 862 必须上"单调队列 + 前缀和"的原因（见 8.2）。
暴力 $O(n^2)$：枚举每个起点 i，向右扩张直到 cur_sum >= target，记录最短。
滑窗优化 $O(n)$：右指针 r 单调右移；左指针 l 在满足条件时单调右移收缩。每个元素至多入/出窗口 1 次，均摊 $O(n)$。
Python 工业级实现
from typing import List
class Solution:
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
n = len(nums)
l, cur_sum = 0, 0
ans = n + 1 # 初值: n+1 是"不可能值"
for r, x in enumerate(nums):
cur_sum += x # 1) in: 右端纳入
while cur_sum >= target: # 2) shrink: 满足时收缩
ans = min(ans, r - l + 1) # 先 update 再 shrink
cur_sum -= nums[l]
l += 1
return ans if ans <= n else 0 # 3) 兜底: 无解返回 0C++ 备份实现
#include <vector>
#include <climits>
using namespace std;
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int n = nums.size(), l = 0, cur_sum = 0;
int ans = n + 1; // 不可能值
for (int r = 0; r < n; ++r) {
cur_sum += nums[r]; // in
while (cur_sum >= target) { // satisfied: 收缩
ans = min(ans, r - l + 1); // 先 update
cur_sum -= nums[l++]; // 再 shrink
}
}
return ans <= n ? ans : 0; // 兜底
}
};代码逐段讲解
变量含义：
cur_sum：窗口内元素之和，是这道题的核心状态l：闭区间左边界，nums[l .. r]是当前窗口ans：从初值n+1单调不增地记录历史最短长度
ans = n + 1 这个初值——为什么不用 INT_MAX？ 因为任何合法答案 ≤ n（窗口最大就是整个数组），用 n+1 作"不可能值"既能区分有解/无解，又避免溢出——后面 ans + 任何加法 都不会爆 int。LeetCode 上喜欢这种"贴着上界 +1"的初值，比 INT_MAX 更安全。Python 里没溢出风险但仍推荐这个写法，让 C++/Java 移植零负担。
while cur_sum >= target 是 satisfied 判定——这是"求最短"模板的标志。别写成 not_satisfied()：那是上一节求最长的写法，套到这里会变成"和不够大就收缩"，直接死循环或永不进入。
update 在 shrink 之前 —— 保证 r - l + 1 是"当前合法窗口"的长度。如果反过来先 shrink 再 update，l 已经前进、cur_sum 已经减小，此时窗口可能已经不合法，update 出来的不是"满足条件的最短长度"而是一个无意义的值。
循环不变量：每次进入 while 时，cur_sum >= target 且 nums[l..r] 是合法窗口。这是 ans = min(ans, r - l + 1) 那一行能直接信任的前提。
兜底 return ans <= n ? ans : 0：若全数组之和都小于 target，while 永远不会进入，ans 保持 n+1，此时返回 0。少了这个兜底，无解的 case 会返回 n+1（错答）。
5. 复杂度分析
- 时间复杂度：$O(n)$ — 均摊证明同上一节：右指针
r从 0 走到 n-1 共 n 步；左指针l全程单调右移，最坏也只走 n 步。每个元素最多入窗口 1 次（cur_sum += x）、出窗口 1 次（cur_sum -= nums[l]），总操作数 $\leq 2n = O(n)$。 - 空间复杂度：$O(1)$ — 只有
l、cur_sum、ans几个标量，没有任何辅助容器。这是 LC 209 比 LC 3 更"轻"的地方。 - 暴力 $O(n^2)$ vs. 滑窗 $O(n)$ 的真实差距：暴力枚举起点 i 后向右累加，最坏退化到 $O(n^2)$。当 $n = 10^5$（LC 209 实际约束）时暴力是 $10^10$ 次操作，直接 TLE；滑窗只要 $10^5$ 次，毫秒级返回。
在 Bloomberg 的实时交易流"找最短窗口满足成交额阈值"、Google Ads 的"最短广告位组合达到 CPM 目标"等场景中，这套模板就是骨架。
6. 易错点小结
把这 4 条贴在显示器上：
ans初值用n+1或INT_MAX，绝不能用0—min(0, anything)永远是 0，会把所有答案污染成 0。这是新人最高发的 bug。- while 条件：求最短是
satisfied()，求最长是not_satisfied()，别写反。写反了求最短会变成"不满足就收缩"，左指针根本不会前进、窗口只增不减，要么死循环要么全错。 - update-ans 位置：求最短必须在 while 内、shrink 前；求最长在 while 外。位置错了会得到"少算一格"或"多算一格"的非最优解。
- 兜底返回：无解时（
ans未被任何min更新过、仍为初值n+1）必须return 0，不能直接return ans，否则会返回n+1这个非法值。
7. 热身题：LC 1234 Replace the Substring for Balanced String
题目：字符串 s 只含 'Q'、'W'、'E'、'R' 四种字符，长度 n 是 4 的倍数。要求每种字符恰好出现 n/4 次才算"平衡"。可以替换一个连续子串为任意字符（任意字符可以任选），求最短替换长度。若已平衡返回 0。
关键洞察：把题面翻译成滑窗约束——窗口外每种字符的频次都 ≤ n/4 时，窗口内的所有字符都可以替换成任意字符使整体平衡（因为窗口长度足够，且窗口外没有"超额"字符）。问题立刻变成：
"求最短的窗口，使得窗口外所有字符的频次都 ≤ n/4。"
这一步"问题翻译"是 Big Tech 算法面试常考察的能力——把原题改写成"找最短/最长合法窗口"的能力比硬记模板更值钱。
from collections import Counter
class Solution:
def balancedString(self, s: str) -> int:
n = len(s)
target = n // 4
cnt = Counter(s) # 全局频次 = 窗口外频次 (初始窗口为空)
# 已平衡 corner case: 直接返回 0
if all(cnt[c] <= target for c in "QWER"):
return 0
l, ans = 0, n
for r, ch in enumerate(s):
cnt[ch] -= 1 # in: 进入窗口 → 窗口外频次 -1
while all(cnt[c] <= target for c in "QWER"): # satisfied
ans = min(ans, r - l + 1) # 先 update
cnt[s[l]] += 1 # 再 shrink: l 离开窗口 → 窗口外频次 +1
l += 1
return ans5 行讲解：
cnt维护的不是"窗口内"频次，而是"窗口外"频次——元素进窗口时-= 1、离开窗口时+= 1，方向反过来satisfied= 窗口外每种字符都 ≤ n/4 = 窗口可以"消化"掉超额部分- update 在 shrink 之前，标准的"求最短"模板套路
all(...)内层只遍历 4 个字符（"QWER"），常数 4，仍是 $O(n)$- 这是"问题翻译能力"的范本题——把"替换连续子串使平衡"翻译成"窗口外频次受限"，是 Bloomberg / Google 风格