LeetCode 862. 和至少为 K 的最短子数组
题目描述
题意分析
在数组中找一段连续、非空的子数组，使元素和至少为
k，返回符合条件的最短长度；不存在则返回-1。数组允许负数，不能把普通正数数组的滑动窗口直接套过来。加入负数可能让窗口和变小，删除负数又可能让窗口和变大，因此“当前不达标就扩大、达标就收缩”没有单调保证。可以用前缀和表示任意子数组的和，再只保留那些未来仍可能成为最优起点的位置。
解法：前缀和 + 单调队列
核心思路
[!blue]
定义
prefix[i]为前i个元素之和，prefix[0] = 0。子数组[j, i)的和是prefix[i] - prefix[j]，长度是i - j。从左到右枚举终点i，需要在此前的位置中寻找满足差值至少为k的起点，并让起点尽量靠后。用双端队列保存候选起点下标，下标按加入顺序递增，同时让对应的前缀和也严格递增。前缀和越小，越容易与当前或未来的终点组成达标区间；下标越靠后，形成的区间越短。两项优势都不如另一个候选的位置，可以安全删除。
先检查队首。它的前缀和最小，最容易达标；如果它与当前
i的差值仍不足k，后面更大的前缀和也都不满足。如果队首达标，记录长度后将它弹出，再继续检查新的队首，因为后面的起点更靠右，可能给出更短答案。为什么达标后可以永久删除这个起点？它已经遇到了最早可行终点，当前长度也已计入答案；以后终点只会更靠右，同一起点产生的长度只会更长，不可能改善这次结果。因此前端删除不会丢失最优答案，但必须先更新答案再删除。
接着为当前下标入队做准备。若旧队尾
j满足prefix[j] >= prefix[i]，当前位置i就完全更有利：对任意未来终点t，从i开始的区间和不小于从j开始的区间和，而长度更短。旧队尾不再有保留价值，可以不断弹出，直到前缀和重新严格递增。最后才把
i加入队尾，使本轮计算只使用早于i的起点，保证区间非空。下标0也按同样流程入队，才能表示从数组首元素开始的区间；终点需要枚举到n，才能覆盖在数组末尾结束的区间。前端删除的是已经得到最短可行结果的起点，后端删除的是被更晚、更小前缀支配的起点。所有被排除的位置都有充分理由，其余候选按单调顺序继续参与比较，因此取扫描过程中的最小长度即可得到全局答案。
解题步骤
- 使用
long/int64构建长度为n + 1的前缀和数组，初始化空双端队列与答案n + 1。- 从
i = 0枚举到n，不断检查队首；满足prefix[i] - prefix[队首] >= k时，先更新长度再弹出队首。- 不断弹出前缀和大于等于
prefix[i]的队尾下标，删除被当前候选支配的位置。- 将当前下标
i加入队尾。- 最后若答案仍为
n + 1，返回-1；否则返回最短长度。
代码实现
class Solution {
public int shortestSubarray(int[] nums, int k) {
int n = nums.length;
long[] prefix = new long[n + 1];
for (int i = 0; i < n; i++) {
prefix[i + 1] = prefix[i] + nums[i];
}
Deque<Integer> deque = new ArrayDeque<>();
int ans = n + 1;
for (int i = 0; i <= n; i++) {
while (!deque.isEmpty() && prefix[i] - prefix[deque.peekFirst()] >= k) {
// 这个起点已遇到最早可行终点，未来区间只会更长，可以结算后删除。
ans = Math.min(ans, i - deque.pollFirst());
}
while (!deque.isEmpty() && prefix[deque.peekLast()] >= prefix[i]) {
// 当前前缀更小或相等且下标更晚，完全优于旧队尾。
deque.pollLast();
}
deque.offerLast(i);
}
return ans == n + 1 ? -1 : ans;
}
}
func shortestSubarray(nums []int, k int) int {
n := len(nums)
prefix := make([]int64, n+1)
for i, num := range nums {
prefix[i+1] = prefix[i] + int64(num)
}
deque := make([]int, 0, n+1)
ans := n + 1
for i := 0; i <= n; i++ {
for len(deque) > 0 &&
prefix[i]-prefix[deque[0]] >= int64(k) {
if i-deque[0] < ans {
ans = i - deque[0]
}
// 这个起点已遇到最早可行终点，未来区间只会更长，可以结算后删除。
deque = deque[1:]
}
for len(deque) > 0 &&
prefix[deque[len(deque)-1]] >= prefix[i] {
// 当前前缀更小或相等且下标更晚，完全优于旧队尾。
deque = deque[:len(deque)-1]
}
deque = append(deque, i)
}
if ans == n+1 {
return -1
}
return ans
}
复杂度分析
- 时间复杂度：$O(n)$。每个前缀下标只入队一次，并且最多从队首或队尾弹出一次；两个
while的总执行次数是线性的。- 空间复杂度：$O(n)$。前缀和数组和双端队列最多各保存
n + 1个元素。
关键点总结
[!green]
- 含负数时窗口和不单调，不能照搬全正数数组的滑动窗口。
- 队列存下标，且对应的前缀和严格递增。
- 队首负责结算已经达标的区间；队尾负责删除被当前前缀全面支配的候选。
- 两处都必须使用
while，因为一次可能淘汰多个候选。- 前缀和最坏可达 $10^{10}$，必须使用 64 位整数。
易错点总结
[!yellow]
- 照搬正数滑动窗口：负数会改变加入、删除元素时窗口和的变化方向，普通收缩规则不再保证正确。
- 前缀和使用 32 位整数：题目范围下累加值可达到 $10^{10}$，Java 应用
long，Go 应用int64。- 队首或队尾只删除一次：同一个终点可能使多个起点达标，也可能同时支配多个队尾，两个位置都需要循环处理。
- 队首弹出前没有记录长度：这个起点不会再参与后续比较，必须先保留本轮答案。
- 队列只保存和值：计算区间长度还需要下标，因此队列应保存前缀位置。
- 遗漏首个或最后一个前缀位置：
0对应从数组开头出发，n对应在数组末尾结束，两者都要处理。- 相等前缀保留较早位置：较晚位置能形成更短区间，使用
>=删除旧队尾可去掉无优势候选。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 209. 长度最小的子数组 | 中等 | 原题元素为正可用普通滑动窗口，本题允许负数，需前缀和与单调队列维护候选。 |
| 239. 滑动窗口最大值 | 困难 | 同样利用单调队列淘汰永不更优的位置，本题比较前缀和及下标，原题比较窗口元素大小。 |
| 1438. 绝对差不超过限制的最长连续子数组 | 中等 | 用单调队列删除过期且不可能更优的候选；本题按前缀和维护可能的最短区间起点，该题同时维护窗口最大值和最小值。 |