当前:LC209 · 长度最小的子数组 · 首次出现于 Day 5 · 路径:顶栏「56天打卡」→ 点击 LC 题号 → 逐题动画

LC209 · Minimum Size Subarray Sum · 滑窗

长度最小的子数组:和够了就吐左边

元素为正,右端单调吞入只会让和变大;一旦和 ≥ target,左端能吐就吐,吐到不够再继续往右。

右指针扩张并累加。窗口和 ≥ target 时,用当前长度挑战最短,再减去左端、左指针右移,直到和再次不足。元素为正,左端外的更长前缀不必回头看,每个下标最多进窗一次、出窗一次。无解返回 0。时间 O(n),空间 O(1)。

时间 O(n)空间 O(1)结论先行 · 全文约 6 节
导读

这是 LeetCode 209. Minimum Size Subarray Sum。大白话:给你正整数数组 nums 和一个正整数 target,找出和至少为 target 的连续子数组,在所有这样的段里取最短的长度。找不到就返回 0。子数组必须连续,不能跳着捡。

主例 nums = [2, 3, 1, 2, 4, 3],target = 7。[2,3,1,2] 和为 8,长度 4;[1,2,4] 和为 7,长度 3;[4,3] 和为 7,长度 2。答案是 2。单独一个数都小于 7,最短不可能是 1。

枚举左右端再求和是平方级。前缀和加二分能做到 O(n log n),但还没用上「全是正数」。正数让窗口和随左端右移严格变小、随右端右移严格变大,于是同一右端对应的最短合法左端单调,缺口变成一对只前进的指针。

右端吞到和够,这一拍才能缩

left、right 都从 0 起,sum 是闭区间 [left, right] 的和,best 先垫成一个超大数。右指针每步把 nums[right] 加进 sum。和还不到 target,只扩张、不收缩——短窗口都不够,更短的更不够。和一旦 ≥ target,当前窗口是一条合法段,长度 right−left+1 可以去挑战 best,然后才进入收缩。

用手走主例到第一次达标。right=0,sum=2;right=1,sum=5;right=2,sum=6,都不到 7。right=3,加上 2,sum=8。窗口 [2,3,1,2],长度 4,best 写成 4。演示第一帧停在这里:left=0,right=3,和 8,准备收缩。吐掉左端 2,sum=6,left=1。6 < 7,收缩停止。演示第二帧是 [3,1,2],和 6,右端还得继续往右。

若数组里有负数,吐左边可能让和变大,左指针不能只前进,这套滑窗就断了。本题约束正整数,吐左边必然减和,停在「刚好不够」是安全的。

正数前提全为正,收缩左端只会让和变小,所以「缩到不满足就停」不会漏掉更短的合法段。含负数要换前缀和加单调队列,那是另一道题。
右边界扩张使和 ≥ 7
2
0
3
1
1
2
2
3
4
4
3
5
left=0 right=3和 = 8 7和 2+3+1+2=8 ≥ 7 → 收缩

达标就连着吐,吐到不够再扩

收缩是内层循环:只要 sum ≥ target,先用长度更新 best,再 sum -= nums[left],left++。可能连续吐好几个。每一次吐之前的窗口都合法,所以每一次都要记长度,不能只在吐不动时记一次——更短的合法段出现在「还能再吐」的那些中间态。

接着主例。right=4,加上 4,sum=6+4=10,窗口 [3,1,2,4]。先记长度 4,吐 3,sum=7,left=2。演示收缩第一帧:窗口 [1,2,4],和 7,长度 3,best=3。7 仍够,再吐 1,sum=6,left=3,不够了,停。

right=5,加上 3,sum=6+3=9,窗口 [2,4,3],长度 3,best 仍是 3。吐 2,sum=7,left=4。窗口变成 [4,3],长度 2,best=2。演示第二帧就是这一拍。7 仍够,再吐 4,sum=3,left=5,不够。右端走完,答案锁在 2。

每个下标当一次 right 进窗,当一次 left 出窗,总共 2n 次加减,O(n)。找不到任何达标窗口时 best 仍是初值,返回 0,不要返回无穷大。

收缩左边界:每次达标都记录最短长度
2
0
3
1
1
2
2
3
4
4
3
5
left=2 right=4和 = 7 7最短 = 3窗口 [1,2,4] 和 7,长度 3

八行 Go:滑窗

solution.goGo
func minSubArrayLen(target int, nums []int) int {
left, sum, best := 0, 0, math.MaxInt32
for right := 0; right < len(nums); right++ {
sum += nums[right]
for sum >= target {
if right-left+1 < best { best = right - left + 1 }
sum -= nums[left]
left++
}
}
if best == math.MaxInt32 { return 0 }
return best
}

1best 用 MaxInt32 垫上,最后仍是它就返回 0。主例会先后写成 4、3、2。

2外层只负责右端加数。主例 right=3 时 sum 第一次到 8。

3内层在和仍够时先记长度再吐左端。主例 [4,3] 这一拍必须在吐 4 之前记下 2。

4正数保证 left 只增不减。含负数不能用这层循环。

总结

右扩到和够,左缩到和不够,中间每个合法窗口都记长度。主例最短是 [4,3]。

  • 正数让窗口和随两端单调,滑窗才成立。枚举端点是平方,前缀和二分没用上正数。
  • 主例先在 [2,3,1,2] 上和为 8,再在 [1,2,4] 上收到 3,最后 [4,3] 收到 2。
  • 长度要在每次仍达标时记,不能只在吐不动之后记。无解返回 0。
同族题目
LC3无重复字符的最长子串LC76最小覆盖子串LC862和至少为 K 的最短子数组(含负数)