和至少为 K 的最短子数组Java
文章发布较早，内容可能过时，阅读注意甄别。
# 题目
给你一个整数数组 nums 和一个整数 k ，找出 nums 中和至少为 k 的 最短非空子数组 ，并返回该子数组的长度。如果不存在这样的 子数组 ，返回 -1 。
子数组 是数组中 连续 的一部分。
示例 1：
输入：nums = [1], k = 1
输出：1
示例 2：
输入：nums = [1,2], k = 4
输出：-1
示例 3：
输入：nums = [2,-1,2], k = 3
输出：3
提示：
- 1 <= nums.length <= 105
- -105 <= nums[i] <= 105
- 1 <= k <= 109
# 思路
前缀和 + 单调队列
# 解法
class Solution {
public int shortestSubarray(int[] nums, int k) {
// si - sj >= k
int n = nums.length;
long[] sum = new long[n + 1];
for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + nums[i - 1];
LinkedList<Integer> que = new LinkedList<>();
que.addLast(0);
int ans = n + 1;
for (int i = 1; i <= n; i++) {
while (!que.isEmpty() && sum[que.getLast()] >= sum[i]) que.removeLast();
while (!que.isEmpty() && sum[i] - sum[que.getFirst()] >= k) {
ans = Math.min(ans, i - que.getFirst());
que.removeFirst();
}
que.addLast(i);
}
if (ans > n) ans = -1;
return ans;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# 总结
- 分析出几种情况，然后分别对各个情况实现
