LeetCode LCR 008. 长度最小的子数组
题目描述
题意分析
给定正整数数组
nums和正整数target，求和大于或等于目标的最短连续子数组长度。只要求长度，不需要返回具体子数组；没有任何满足条件的区间时返回0。连续表示不能跳过中间元素，达到目标即可，不要求恰好相等。所有元素严格为正，使扩张窗口增加区间和、移除左端减少区间和；下面的滑动窗口和前缀和二分都依赖这个条件。题面另要求尝试
O(n log n)做法，因此同时给出该进阶实现。
解法：正数滑动窗口
核心思路
[!blue]
用
i、j表示当前窗口左右端，s始终等于窗口内元素和。右端每前进一步，就把新元素加进来；和不足目标时，继续去掉左边的正数只会更小，因此需要扩张右端。一旦
s >= target，当前窗口就是一个合法候选，先记录长度，再移除最左元素，尝试能否得到更短的合法窗口。一次扩张后可能连续去掉多个元素而仍然达标，所以这里必须反复收缩，直到和不足目标。为什么左端移走后不用回退？它被移走之前，已经与当时的右端组成合法窗口并记录过答案。今后若仍从这个旧左端出发，只能把右端放得更远，长度一定不会更短，因此没有再考虑它的必要。这样既保留了可能改善答案的候选，也不会重复枚举已无优势的左端。
更新答案必须放在收缩之前，此时窗口仍满足条件。收缩后同步减去被移出的值并移动
i，保持s与窗口一致。目标为正，窗口即使收缩为空，和也会变为零并自然退出循环。左右指针都只向右，每个元素最多加入、移出一次。答案先设为大于任何合法长度的哨兵，若扫描后仍未更新，就按题意返回零；单个元素足够时，主循环也能正常得到长度一。
解题步骤
- 初始化最短长度为哨兵，窗口和为零，左端为零。
- 从左到右移动右端
j，把nums[j]加入窗口和。- 当窗口和达标时，先用
j - i + 1更新答案，再移出nums[i]并右移左端。- 和不足时继续扩张右端，直到完成扫描。
- 未找到合法窗口则返回零，否则返回已记录的最短长度。
代码实现
class Solution {
public int minSubArrayLen(int target, int[] nums) {
final int inf = 1 << 30;
int answer = inf;
int s = 0;
for (int i = 0, j = 0; j < nums.length; ++j) {
s += nums[j];
// 元素全为正，达标后继续收缩仍可能达标，必须用 while。
while (s >= target) {
// 先在窗口仍合法时更新答案，再收缩。
answer = Math.min(answer, j - i + 1);
s -= nums[i++];
}
}
return answer == inf ? 0 : answer;
}
}
func minSubArrayLen(target int, nums []int) int {
const inf = 1 << 30
answer := inf
s, i := 0, 0
for j, x := range nums {
s += x
for s >= target {
answer = min(answer, j-i+1)
s -= nums[i]
i++
}
}
if answer == inf {
return 0
}
return answer
}
复杂度分析
设数组长度为 $n$。
- 时间复杂度：$O(n)$。内层循环的全部执行次数受左端总移动次数限制，不会为每个右端重新扫描数组。
- 辅助空间复杂度：$O(1)$，只维护窗口端点、和与答案。
关键点总结
[!green]
- 正数保证窗口和随扩张增大、随收缩减小。
- 达标时先记录，再持续收缩，寻找更短候选。
- 已移走的左端曾经提供过更短或等长的合法解，今后无需回退。
- 哨兵区分尚无答案与真实长度，最终转换为题目要求的零。
解法二：前缀和 + 二分查找
核心思路
[!blue]
定义
prefix[t]为前t个元素的和，prefix[0] = 0。左闭右开区间[start, end)的和为prefix[end] - prefix[start]，因此达标条件等价于prefix[end] >= prefix[start] + target。固定左端
start后，长度最短就是找到最小的达标右端end。元素都为正，前缀和严格递增，可以二分查找第一个不小于阈值的位置，不必依次尝试全部右端。二分区间设为
[start + 1, n + 1)，其中n + 1作为“没有达标位置”的返回哨兵，不读取这个下标。若找到的位置不超过n，用end - start更新答案；若等于n + 1，说明该左端没有可行后缀。枚举每个左端并取其最短候选，便覆盖全局最短区间。前缀总和可能超过 32 位范围，Java 使用
long、Go 使用int64保存前缀及查询阈值。
解题步骤
- 构造长度为
n + 1的 64 位前缀和数组。- 枚举左端
start，计算阈值prefix[start] + target。- 在后续前缀位置中二分第一个达标位置，保留可能命中的中点，未达标则移到右侧。
- 位置有效时用下标差更新长度，全部左端处理后返回最短值或零。
代码实现
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int n = nums.length;
long[] prefix = new long[n + 1];
for (int i = 0; i < n; i++) {
prefix[i + 1] = prefix[i] + nums[i];
}
int answer = n + 1;
for (int start = 0; start < n; start++) {
long threshold = prefix[start] + target;
int left = start + 1;
int right = n + 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (prefix[mid] >= threshold) {
right = mid;
} else {
left = mid + 1;
}
}
if (left <= n) {
answer = Math.min(answer, left - start);
}
}
return answer == n + 1 ? 0 : answer;
}
}
func minSubArrayLen(target int, nums []int) int {
n := len(nums)
prefix := make([]int64, n+1)
for i, value := range nums {
prefix[i+1] = prefix[i] + int64(value)
}
answer := n + 1
for start := 0; start < n; start++ {
threshold := prefix[start] + int64(target)
left, right := start+1, n+1
for left < right {
mid := left + (right-left)/2
if prefix[mid] >= threshold {
right = mid
} else {
left = mid + 1
}
}
if left <= n && left-start < answer {
answer = left - start
}
}
if answer == n+1 {
return 0
}
return answer
}
复杂度分析
- 时间复杂度：$O(n\log(n+1))$，构造前缀后，对每个左端进行一次二分。
- 辅助空间复杂度：$O(n)$，保存全部前缀和。
关键点总结
[!green]
- 将区间和约束改写为前缀阈值，再用递增性查找最早达标右端。
- 查询含等号，右端使用前缀位置，长度直接是
end - start。n + 1只作未找到的哨兵，不访问该数组位置。
易错点总结
[!yellow]
- 用
if只收缩一次可能漏掉更短区间，达标后要持续尝试。- 缩窗之后才无条件记录长度，可能把已经不满足目标的区间当成答案。
- 移动左端时必须同步减去对应元素，不能破坏窗口和定义。
- 元素为正是两种方法的前提，允许负数时不能直接沿用当前移动或二分规则。
- 前缀和二分查询的是第一个大于等于阈值的位置，不是必须恰好等于阈值。
- 前缀总和可能达到
10^10，二分版本应使用 64 位前缀；原窗口版本及时收缩，窗口和小于目标后最多再增加一个元素，不会累积整个大总和。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 862. 和至少为 K 的最短子数组 | 困难 | 原题允许负数，普通滑动窗口失去单调性，需要前缀和与单调队列。 |
| 713. 乘积小于 K 的子数组 | 中等 | 同样在正数条件下维护窗口，本题约束和达到下界，原题约束乘积低于上界。 |