LeetCode 209. 长度最小的子数组
题目描述
题意分析
在正整数数组中寻找一个连续、非空的片段，要求元素和大于或等于正整数
target，返回满足条件的最短长度。和恰好等于目标也算达标，不能跳过中间元素；如果不存在这样的片段，返回0。数组元素全部为正是关键条件，决定了扩张或缩短片段时总和如何变化。题目还要求在实现线性时间解法后，尝试给出 $O(n\log n)$ 的解法，下面分别说明滑动窗口和前缀和二分。
解法：滑动窗口收缩满足条件的区间
核心思路
[!blue]
用闭区间
[left, right]表示当前窗口，sum保存窗口内元素之和。右端加入一个正数时总和变大，左端移出一个正数时总和变小，所以当窗口不达标时，继续移出左端不会让它达标，只能向右扩张。每次加入
nums[right]后，只要sum >= target，当前窗口就是合法候选。先用right - left + 1更新最短长度，再移出nums[left]并将左端前移。如果缩短后的窗口仍达标，就继续记录和收缩；直到窗口首次不达标时停止。对于这个右端点，更靠右的左端只会使总和更小，因此本轮已经不能再缩短。左指针为什么不需要回退？某个左端被移走之前，必然已经记录过一个以它开头的合法窗口。以后再固定这个旧左端、把右端延长，长度只会更大，不可能改善已经记录的答案。因此这些旧左端可以永久舍弃，后续只需继续探索还没有被排除的更短窗口。
ans用n + 1表示尚未找到答案，因为任何非空子数组的长度都不超过n。两个指针只向右移动，每个元素最多加入和移出一次，所以持续收缩的内层循环不会把总时间变成平方级。
解题步骤
- 初始化
left = 0、sum = 0，用ans = n + 1标记暂无答案。- 右指针依次经过每个元素，并将当前值加入
sum。- 当
sum >= target时，先记录当前合法长度，再从和中减去左端元素并右移left。- 第 3 步要连续执行，直到窗口不再达标，再继续扩张右端。
- 扫描结束后，若
ans仍为初始哨兵则返回0，否则返回最短长度。
代码实现
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int left = 0;
int sum = 0;
int ans = nums.length + 1;
for (int right = 0; right < nums.length; right++) {
sum += nums[right];
// 当前窗口合法时先记录，再连续收缩到不达标。
while (sum >= target) {
ans = Math.min(ans, right - left + 1);
sum -= nums[left++];
}
}
return ans == nums.length + 1 ? 0 : ans;
}
}
func minSubArrayLen(target int, nums []int) int {
left := 0
sum := 0
ans := len(nums) + 1
for right := 0; right < len(nums); right++ {
sum += nums[right]
// 当前窗口合法时先记录，再连续收缩到不达标。
for sum >= target {
if right-left+1 < ans {
ans = right - left + 1
}
sum -= nums[left]
left++
}
}
if ans == len(nums)+1 {
return 0
}
return ans
}
复杂度分析
- 时间复杂度：$O(n)$。右指针前进
n次，左指针累计也至多前进n次，嵌套循环的总操作数仍为线性。- 空间复杂度：$O(1)$，只保存窗口边界、总和与答案。
关键点总结
[!green]
- 正数保证扩张增大总和、收缩减小总和，才能按单一方向调整窗口。
- 达标时先记录再收缩，持续寻找当前右端下的更短合法窗口。
- 被移出的左端已经参与过更短的合法区间，后续不需要回退检查。
- 答案哨兵必须与无解时要求返回的
0区分。
解法：前缀和加二分查找
核心思路
[!blue]
用
prefix[i]表示前i个元素的和，额外保留prefix[0] = 0。固定子数组左端left，令右端的后一位为j，则区间和为prefix[j] - prefix[left]，达标条件可以改写成prefix[j] >= prefix[left] + target。对固定左端，长度为
j - left，因此需要找到满足不等式的最小j。数组元素全为正，前缀和严格递增，可以在下标区间[left + 1, n]中二分第一个大于等于prefix[left] + target的位置。这就是该左端对应的最短合法片段。二分维护左闭右开的候选范围
[low, high)，初始low = left + 1、high = n + 1。若中点前缀和已达标，答案可能就是中点，也可能更早，令high = mid；若未达标，中点及其左侧都不可能满足，令low = mid + 1。最终两端重合的位置若为n + 1，表示这个左端没有合法右端，不能计入答案。枚举每一个左端并取其最短合法长度的最小值，就覆盖了所有可能的最优区间。前缀和只需计算一次，每个左端做一次二分，总时间为 $O(nlog n)$，满足题目要求的另一种解法。
解题步骤
- 创建长度为
n + 1的prefix，令prefix[i + 1] = prefix[i] + nums[i]。- 将答案初始化为
n + 1，依次枚举left从0到n - 1。- 计算需要达到的前缀和
needed = prefix[left] + target，在[left + 1, n + 1)中二分第一个前缀和不小于它的位置。- 二分结束后，只有
low <= n才存在合法片段，用low - left更新答案。- 若所有左端都无解，返回
0；否则返回已记录的最短长度。
代码实现
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int n = nums.length;
int[] prefix = new int[n + 1];
for (int i = 0; i < n; i++) {
prefix[i + 1] = prefix[i] + nums[i];
}
int ans = n + 1;
for (int left = 0; left < n; left++) {
int needed = prefix[left] + target;
int low = left + 1;
int high = n + 1;
while (low < high) {
int mid = low + (high - low) / 2;
if (prefix[mid] >= needed) {
high = mid;
} else {
low = mid + 1;
}
}
if (low <= n) {
ans = Math.min(ans, low - left);
}
}
return ans == n + 1 ? 0 : ans;
}
}
func minSubArrayLen(target int, nums []int) int {
n := len(nums)
prefix := make([]int, n+1)
for i, num := range nums {
prefix[i+1] = prefix[i] + num
}
ans := n + 1
for left := 0; left < n; left++ {
needed := prefix[left] + target
low := left + 1
high := n + 1
for low < high {
mid := low + (high-low)/2
if prefix[mid] >= needed {
high = mid
} else {
low = mid + 1
}
}
if low <= n && low-left < ans {
ans = low - left
}
}
if ans == n+1 {
return 0
}
return ans
}
复杂度分析
- 时间复杂度：$O(nlog n)$，建立前缀和需 $O(n)$，每个左端对应一次对数时间二分。
- 空间复杂度：$O(n)$，来自长度为
n + 1的前缀和数组。
关键点总结
[!green]
- 前缀下标表示元素个数，原数组区间
[left, j - 1]的长度是j - left。- 正数保证前缀和递增，固定左端后，合法右端构成一段后缀，可以二分其最左位置。
- 找的是第一个大于等于目标的位置，而不是只找相等值。
n + 1同时作为二分的右开边界和找不到合法右端的标记，不访问该下标。
易错点总结
[!yellow]
- 滑动窗口只用
if收缩一次，会漏掉同一个右端下还能继续缩短的合法窗口。- 先收缩再无条件更新答案，可能记录一个已经不达标的区间；必须在合法时记录长度。
- 把判断写成
sum > target，会漏掉和刚好等于目标的区间。- 前缀和二分应查找第一个大于等于目标的位置，只查找恰好相等会漏掉总和超过目标的合法区间。
- 前缀下标
j表示原数组右端的后一位，区间长度是j - left，不能再加一。- 两种解法都利用正数带来的单调性；含负数时不能直接沿用窗口或对原前缀数组二分。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 862. 和至少为 K 的最短子数组 | 困难 | 原题允许负数，普通滑动窗口失去单调性，需要前缀和与单调队列。 |
| 713. 乘积小于 K 的子数组 | 中等 | 同样在正数条件下维护窗口，本题约束和达到下界，原题约束乘积低于上界。 |