题目描述
思路解析动画文字版
枚举每个起点终点再求和,n² 甚至 n³,还重复加了很多次。换个思路:用一个窗口,右边扩进新数、和够了就从左边缩,每个数只被加一次、减一次,全程只扫一遍。
r 不断右移把数加进窗口;和不够 target 时只能继续扩,一旦窗口和 ≥ target,就记录长度、并尽量把 l 右移缩短窗口(同时减去左端值),直到和不够再继续扩。最短的达标窗口就在「每次刚好够」的瞬间出现。
r=0 · 和不够:负例分支:窗口只有 [2],和 2 还远不到 7,没法缩、只能继续右扩。和不够时左指针绝不动。
r=1 · 还是不够:吃进 3,窗口 [2,3] 和 5,仍不够 7。继续右扩,l 不动。
r=2 · 仍不够:再吃进 1,和 6,就差一点点,还是不够。再扩。
r=3 · 够了!:吃进 2,和 8 第一次 ≥ 7!记下长度 4,现在该缩左看能不能更短。
r=3 · 缩左 → 不够停:把左端 2 移出,和降到 6 小于 7,缩不动了,停。当前最短仍是 4,回去继续右扩。
r=4 · 又够了:r 扩到 4,吃进 4,窗口 [3,1,2,4] 和 10 ≥ 7。又能缩左了。
r=4 · 缩到长度 3:连缩:去掉 3 后 [1,2,4]=7 仍达标,刷新最短为 3;再去掉 1 后 [2,4]=6 不够,停在 l=3。最短已是 3。
r=5 · 最后一次扩:r 扩到最后,吃进 3,窗口 [2,4,3] 和 9 ≥ 7,继续缩左找更短。
r=5 · 缩到最短 [4,3]:去掉左端 2 后窗口 [4,3]=7 ≥ 7,长度 2!这是全程最短,就是答案。
「连续子数组 + 满足某条件求最长/最短」就用滑动窗口:右扩纳入、违规/达标就动左边。无重复最长子串、最小覆盖子串都是它。
参考代码
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复杂度
- 时间复杂度:O(n),l 只增不减、r 只走一遍,两根指针合计移动不超过 2n
- 空间复杂度:O(1),只用 l、s、best 几个变量
可套用的代码模板
记住骨架:r 右扩纳入、while 里左缩、缩前/后更新答案。求最短在「达标」时更新、求最长在「违规」前更新,是两类窗口的区别。
Python
# 「连续子数组/子串 + 求最长/最短」都套l = 0for r in range(n): 加入(nums[r]) # 右扩 while 窗口违规 or 已达标: # 该缩了 更新答案() 移出(nums[l]); l += 1 # 左缩易错点
这道题到这就讲完了。动画和文字是同一套思路——别光看,关掉页面自己默写一遍。然后顺着主线继续:
替换后的最长重复字符
LeetCode 424 · 中等 · 沿着 滑动窗口套路 继续往下推进
把这道题真正学会,再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解(全站陆续覆盖)
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告,记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法,几十万开发者在看的算法讲解
想成体系刷透这类套路?去图解算法专题