题目描述
思路解析动画文字版
记住这条「右扩累加、够了就左缩」,下面每一帧都在套它。
右指针扩到下标 0(值 4),累加进窗口 → 窗口和 4。还不够 11,继续右扩。
右指针扩到下标 1(值 2),累加进窗口 → 窗口和 6。还不够 11,继续右扩。
右指针扩到下标 2(值 1),累加进窗口 → 窗口和 7。还不够 11,继续右扩。
右指针扩到下标 3(值 3),累加进窗口 → 窗口和 10。还不够 11,继续右扩。
右指针扩到下标 4(值 2),累加进窗口 → 窗口和 12。已经够 11 了,准备收缩左边求更短。
收缩前先记下长度 5,刷新最短为 5;左指针缩到下标 1,移出后窗口和 8 < 11,这一轮缩不动了,回去继续右扩。
右指针扩到下标 5(值 5),累加进窗口 → 窗口和 13。已经够 11 了,准备收缩左边求更短。
左指针缩到下标 2,移出后窗口和 11 仍 ≥ 11,还能再缩。
收缩前先记下长度 4,刷新最短为 4;左指针缩到下标 3,移出后窗口和 10 < 11,这一轮缩不动了,回去继续右扩。
右指针扩到下标 6(值 1),累加进窗口 → 窗口和 11。已经够 11 了,准备收缩左边求更短。
左指针缩到下标 4,移出后窗口和 8 < 11,这一轮缩不动了,回去继续右扩。
右指针扩到下标 7(值 2),累加进窗口 → 窗口和 10。还不够 11,继续右扩。
右指针扩到下标 8(值 3),累加进窗口 → 窗口和 13。已经够 11 了,准备收缩左边求更短。
左指针缩到下标 5,移出后窗口和 11 仍 ≥ 11,还能再缩。
左指针缩到下标 6,移出后窗口和 6 < 11,这一轮缩不动了,回去继续右扩。
右指针扩到下标 9(值 1),累加进窗口 → 窗口和 7。还不够 11,继续右扩。
右指针扩到下标 10(值 4),累加进窗口 → 窗口和 11。已经够 11 了,准备收缩左边求更短。
左指针缩到下标 7,移出后窗口和 10 < 11,这一轮缩不动了,回去继续右扩。
右指针扩到下标 11(值 2),累加进窗口 → 窗口和 12。已经够 11 了,准备收缩左边求更短。
左指针缩到下标 8,移出后窗口和 10 < 11,这一轮缩不动了,回去继续右扩。
整趟扫完,最短的「和 ≥ 11」窗口长度是 4(绿色高亮)。左右指针各只走一遍,O(n)。
边界先想清:凑不够返回 0,单元素也可能就是答案。
两个高频追问,区分滑动窗口的适用边界。
参考代码
def minSubArrayLen(target, nums): l = s = 0 best = float("inf") for r in range(len(nums)): s += nums[r] # 右扩累加 while s >= target: # 够了就收缩 best = min(best, r - l + 1) s -= nums[l]; l += 1 return 0 if best == float("inf") else best复杂度
- 时间:O(n),l、r 各最多走一遍,合计线性
- 空间:O(1),只用几个指针/累加变量
易错点
面试追问把动画讲成自己的话
追问如果数组里有负数还能用滑动窗口吗?
追问能不能用前缀和 + 二分做到 O(n log n)?
这道题到这就讲完了。动画和文字是同一套思路——别光看,关掉页面自己默写一遍。然后顺着主线继续:
替换后的最长重复字符
LeetCode 424 · 中等 · 沿着 滑动窗口套路 继续往下推进
把这道题真正学会,再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解(全站陆续覆盖)
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告,记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法,几十万开发者在看的算法讲解
想成体系刷透这类套路?去图解算法专题