LeetCode 209中等滑动窗口
长度最小的子数组 图解题解
这道题到底在问什么
正整数数组中，求和 ≥ target 的最短连续子数组长度(没有返回 0)。
- nums
- [2, 3, 1, 2, 4, 3]
- target
- 7
- 输出
- 2 （子数组 [4, 3]，和 7 ≥ 7）
先想最直接的笨办法
枚举每个起点终点再求和，n² 甚至 n³，还重复加了很多次。换个思路：用一个窗口，右边扩进新数、和够了就从左边缩，每个数只被加一次、减一次，全程只扫一遍。（动画第 3 步）
最优解：一步一步想明白
- 3枚举每个起点终点再求和，n² 甚至 n³，还重复加了很多次。换个思路：用一个窗口，右边扩进新数、和够了就从左边缩，每个数只被加一次、减一次，全程只扫一遍。
- 4r 不断右移把数加进窗口；和不够 target 时只能继续扩，一旦窗口和 ≥ target，就记录长度、并尽量把 l 右移缩短窗口(同时减去左端值)，直到和不够再继续扩。最短的达标窗口就在「每次刚好够」的瞬间出现。
- 5和 = 2 小于 7负例分支：窗口只有 [2]，和 2 还远不到 7，没法缩、只能继续右扩。和不够时左指针绝不动。
- 6和 = 2+3 = 5 小于 7吃进 3，窗口 [2,3] 和 5，仍不够 7。继续右扩，l 不动。
- 7和 = 5+1 = 6 小于 7再吃进 1，和 6，就差一点点，还是不够。再扩。
- 8和 = 6+2 = 8 ≥ 7吃进 2，和 8 第一次 ≥ 7！记下长度 4，现在该缩左看能不能更短。
- 9减 2 → 和 6 小于 7把左端 2 移出，和降到 6 小于 7，缩不动了，停。当前最短仍是 4，回去继续右扩。
- 10和 = 6+4 = 10 ≥ 7r 扩到 4，吃进 4，窗口 [3,1,2,4] 和 10 ≥ 7。又能缩左了。
- 11减 3 → [1,2,4]=7，长度 3连缩：去掉 3 后 [1,2,4]=7 仍达标，刷新最短为 3；再去掉 1 后 [2,4]=6 不够，停在 l=3。最短已是 3。
- 12和 = 6+3 = 9 ≥ 7r 扩到最后，吃进 3，窗口 [2,4,3] 和 9 ≥ 7，继续缩左找更短。
- 13减 2 → [4,3]=7，长度 2去掉左端 2 后窗口 [4,3]=7 ≥ 7，长度 2！这是全程最短，就是答案。
- 16「连续子数组 + 满足某条件求最长/最短」就用滑动窗口：右扩纳入、违规/达标就动左边。无重复最长子串、最小覆盖子串都是它。
⚠️ 容易写错的地方
✗ 错：缩窗口时只 l += 1，忘了 s -= nums[l]
✓ 对：先 s -= nums[l] 再 l += 1
窗口和必须和窗口同步维护；不减左端值，s 会一直偏大、while 永远成立，把窗口缩成空甚至越界
✗ 错：没找到也返回 best（inf）
✓ 对：最后判 inf 返回 0
题目要求无解时返回 0，直接返回 inf 是错的
✗ 错：收缩用 if 只缩一次
✓ 对：用 while 一直缩到不达标
一次右扩后可能要连缩好几格（如 r=4 时连缩 3 和 1）
完整代码（Python）
Python
class Solution:
def minSubArrayLen(self, target, nums):
l = 0
total = 0
ans = len(nums) + 1
for r, x in enumerate(nums):
total += x
while total >= target:
ans = min(ans, r - l + 1)
total -= nums[l]
l += 1
return 0 if ans == len(nums) + 1 else ans套路模板 · 滑动窗口「右扩 + 左缩」（背下来）
# 「连续子数组/子串 + 求最长/最短」都套
l = 0
for r in range(n):
加入(nums[r]) # 右扩
while 窗口违规 or 已达标: # 该缩了
更新答案()
移出(nums[l]); l += 1 # 左缩复杂度
时间复杂度
O(n)
l 只增不减、r 只走一遍，两根指针合计移动不超过 2n
空间复杂度
O(1)
只用 l、s、best 几个变量
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 长度最小的子数组 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
这道题为什么用「滑动窗口」，换最直接的暴力解会差在哪？+
滑动窗口抓住了本题的结构特征，把暴力解里重复的工作省掉；暴力解通常要多嵌套一层枚举，数据一大就超时。具体对比见上文「暴力解及其卡点」与「最优解逐步推演」两节。
时间复杂度为什么是 undefined？怎么推出来的？+
按上文复杂度小节的推导，时间复杂度为 undefined。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。