长度最小的子数组:和够了就吐左边
元素为正,右端单调吞入只会让和变大;一旦和 ≥ target,左端能吐就吐,吐到不够再继续往右。
右指针扩张并累加。窗口和 ≥ target 时,用当前长度挑战最短,再减去左端、左指针右移,直到和再次不足。元素为正,左端外的更长前缀不必回头看,每个下标最多进窗一次、出窗一次。无解返回 0。时间 O(n),空间 O(1)。
这是 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,右端还得继续往右。
若数组里有负数,吐左边可能让和变大,左指针不能只前进,这套滑窗就断了。本题约束正整数,吐左边必然减和,停在「刚好不够」是安全的。
正数前提全为正,收缩左端只会让和变小,所以「缩到不满足就停」不会漏掉更短的合法段。含负数要换前缀和加单调队列,那是另一道题。
达标就连着吐,吐到不够再扩
收缩是内层循环:只要 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,不要返回无穷大。
八行 Go:滑窗
func minSubArrayLen(target int, nums []int) int {left, sum, best := 0, 0, math.MaxInt32for 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。