一、题目
给你一个整数数组 nums 和一个整数 k ，找出 nums 中和至少为 k 的 最短非空子数组 ，并返回该子数组的长度。如果不存在这样的 子数组 ，返回 -1 。
子数组 是数组中 连续 的一部分。
二、示例
2.1> 示例 1：
【输入】nums = [1], k = 1
【输出】1
2.2> 示例 2：
【输入】nums = [1,2], k = 4
【输出】-1
2.3> 示例 3：
【输入】nums = [2,-1,2], k = 3
【输出】3
提示：
-
1<= nums.length <=10^5 -
-10^5<= nums[i] <=10^5 -
1<= k <=10^9
三、解题思路
根据题目描述，我们要找到N个子序列，并且要求子序列的总和要大于等于k，并且只要最短长度。那么，对于一个数组有多少子序列，我们首先需要确定数组子序列的起点。那么，由于题目中只需要最短长度，所以，假设我们以i为起点向后拼装子序列，只要子序列总和大于等于k，则立刻结束以i为起点的子序列组合行为。具体如下图所示：
为了避免不同起点执行拼装子序列会产生重复操作，所以，我们采取前缀和的方式，即：计算位置i之前的所有元素之和。以nums=[2, -1, 2, 3, 4]为例，对应的前缀和就是[0, 2, 1, 3, 6, 10]。我们通过遍历数组nums的前缀和，将某个元素i的前缀和放入到队列中，这样，从末尾执行插入，从队首执行弹出。
那么，其实对于哪些数为起点，也是有优化空间的。就是说，以下图所示，当我们发现E的前缀和sum(A-D)大于等于F的前缀和sum(A-E)，我们其实就没必要以E为起点了，因为F相比E会更适合。具体逻辑如下图所示：
四、代码实现
class Solution {
public int shortestSubarray(int[] nums, int k) {
int result = Integer.MAX_VALUE, n = nums.length, head = 0, tail = head;
long[] preSum = new long[n + 1];
/** 步骤1：构建前缀和 */
for (int i = 0; i < n; i++) {
if (nums[i] >= k) return 1;
preSum[i + 1] = preSum[i] + nums[i];
}
/** 步骤2：构建单调栈和使用单调栈求最小值 */
int[] queue = new int[n + 1];
for (int i = 0; i < n + 1; i++) {
while (head != tail && preSum[queue[tail - 1]] >= preSum[i])
tail--;
queue[tail++] = i;
while (head != tail && preSum[i] - preSum[queue[head]] >= k)
result = Math.min(i - queue[head++], result);
}
return result == Integer.MAX_VALUE ? -1 : result;
}
}
今天的文章内容就这些了：
写作不易，笔者几个小时甚至数天完成的一篇文章，只愿换来您几秒钟的 点赞 & 分享 。
更多技术干货，欢迎大家关注公众号“爪哇缪斯” ~ \(o)/ ~ 「干货分享，每天更新」
网友评论