LeetCode 862. 和至少为 K 的最短子数组
目录
题目描述
题意分析
要在数组里找一段连续且非空的子数组，使它的元素之和不小于
k，并且在所有满足条件的子数组中长度最短；若一个都不存在就返回-1。注意判据是「至少为k」而不是「恰好等于k」，所以超出得越多也无所谓，只比长度。这道题真正的杀手锏藏在数据范围里：
nums[i]的取值是[-10^5, 10^5]，含负数。这一条直接把 209. 长度最小的子数组 那套双指针滑动窗口判了死刑。209 之所以能滑，是因为元素全为正，窗口和对区间单调——右端点右移和必然变大，左端点右移和必然变小，于是「当前窗口和是否够k」可以指导两根指针单向移动。一旦允许负数，这条单调性彻底崩塌：右扩一格可能让和变小，左缩一格反而可能让和变大，两根指针都失去了移动依据。例如nums = [3, -2, 5]、k = 5，普通滑窗先得到长度 3，移除左端的 3 后窗口和降为 3，便停止收缩，从而错过单元素[5]这个最优答案。换个角度看约束。
n最大 $10^5$，说明目标复杂度是 $O(n)$ 或 $O(n \log n)$，$O(n^2)$ 的 $10^{10}$ 必然超时。k最大 $10^9$，而所有元素之和的绝对值上界是 $10^5 \times 10^5 = 10^{10}$，超出了 32 位整数的范围，所以前缀和必须用 64 位类型存。这是本题少见但致命的一处细节。边界情形：可能无解（如全负数组或所有和都够不到
k），此时返回-1；答案可能是长度为 1 的单个元素（如nums = [1]、k = 1）；答案也可能是整个数组；负数在数组中间时，跨过它反而可能凑出更大的和（[2, -1, 2]的整段和是 3，比任何单元素都大）。
解法：前缀和 + 单调队列
核心思路
令
prefix[i]表示前i个元素之和，则子数组[j, i)的和为prefix[i] - prefix[j]，长度为i - j。问题变成：对每个右端点i，寻找满足prefix[i] - prefix[j] >= k的左端点j，并让距离最短。数组含负数，普通滑动窗口失去单调性：右端加入负数可能让和变小，左端移走负数反而可能让和变大。这里用双端队列保存仍有机会成为最优左端点的前缀下标，并维持两个不变量：
- 队列中的下标递增。
- 这些下标对应的前缀和严格递增。
每轮有两种淘汰：
- 弹队首：若
prefix[i] - prefix[front] >= k，当前区间合法，先更新答案再弹出。对这个左端点来说，当前i已是最早可行的右端点，未来只会得到更长区间；继续弹队首还能尝试更靠后的左端点。- 弹队尾：若
prefix[back] >= prefix[i]，队尾被当前下标支配。当前下标更靠后、前缀和又更小或相等，未来既更容易满足和的要求，也能形成更短区间。正确性：队首弹出的候选已经取得自身最短解，队尾弹出的候选存在全面优于它的新候选，因此删除它们都不会丢失最优答案。其余候选按前缀和递增留在队列中，每个右端点都会结算所有当前可行的左端点，所以全局最短区间一定会被检查到。
解题步骤
- 用
long/int64构建长度为n + 1的前缀和数组，避免累加结果超过 32 位整数。- 初始化空的双端队列和答案
n + 1；队列只保存前缀下标。- 遍历
i = 0...n，先从队首不断弹出所有能与i组成合法区间的下标，并更新最短长度。- 再从队尾弹出所有前缀和不小于
prefix[i]的下标，恢复前缀和严格递增的不变量。- 将
i入队。结束后若答案仍为n + 1，返回-1。例如
nums = [3, -2, 5]，k = 5，前缀和为[0, 3, 1, 6]。处理前缀 1 时，下标 2 从队尾淘汰前缀更大的下标 1；处理前缀 6 时，先用队首下标 0 得到长度 3，再用新的队首下标 2 得到最短长度 1。
代码实现
import java.util.ArrayDeque;
import java.util.Deque;
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个元素。
关键点总结
- 含负数时窗口和不单调，不能照搬全正数数组的滑动窗口。
- 队列存下标，且对应的前缀和严格递增。
- 队首负责结算已经达标的区间；队尾负责删除被当前前缀全面支配的候选。
- 两处都必须使用
while，因为一次可能淘汰多个候选。- 前缀和最坏可达 $10^{10}$，必须使用 64 位整数。
- 面试表达重点是讲清两条弹出规则为何安全，而不是只背出单调队列模板。
易错点总结
- 直接使用滑动窗口：
[3, -2, 5]，k = 5中，收缩时移除正数会让窗口暂时不达标，但继续移除负数又能达标，普通滑窗会错过长度 1 的答案。- 前缀和使用 32 位整数：数据上界可使累加值超过
int范围。- 队首只弹一次：同一个右端点可能对应多个可行左端点，后面的左端点能形成更短区间。
- 队尾比较漏掉等号：相同前缀和应保留更靠后的下标，否则留下的是更差候选。
- 主循环漏掉
i = n：会遗漏所有以数组最后一个元素结尾的答案。- 队列保存前缀和值：没有下标就无法计算区间长度。
- 忘记无解转换：答案保持哨兵值时应返回
-1。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 209. 长度最小的子数组 | 中等 | 元素全为正的版本，窗口和单调，双指针即可，是理解本题「为什么滑窗失效」的对照 |
| 239. 滑动窗口最大值 | 困难 | 单调队列的入门形态，窗口定长，弹出规则由窗口边界和大小关系共同决定 |
| 剑指 Offer 59 - I. 滑动窗口的最大值 | 困难 | 与 239 同题异名，可用来单独打磨双端队列的入队与过期弹出 |
| 剑指 Offer 59 - II. 队列的最大值 | 中等 | 把单调队列封装成支持 push 和 max 的数据结构，考察摊还复杂度的表述 |
| 560. 和为 K 的子数组 | 中等 | 判据换成「恰好等于」且只求个数，前缀和配哈希表，不需要任何单调性 |
| 325. 和等于 k 的最长子数组长度 | 中等 | 同样含负数、同样求长度，但目标是最长且判据为相等，改用哈希表存最早下标 |
| 918. 环形子数组的最大和 | 中等 | 前缀和配单调队列求定长限制内的最优区间，是本题技巧在环形结构上的变体 |
| 1004. 最大连续1的个数 III | 中等 | 约束天然单调，滑动窗口成立，可用来反向确认单调性到底给窗口法提供了什么 |