1.题目

给你一个整数数组 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 <= 10⁵
-10⁵ <= nums[i] <= 10⁵
1 <= k <= 10⁹

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/shortest-subarray-with-sum-at-least-k

2.思路

（1）前缀和
常规想法是使用前缀和数组，即 preSum[i] 保存 nums[0…i - 1] 的前缀和，然后再使用两层 for 循环来遍历所有的子数组，并判断其元素总和是否大于等于 k，如果符合条件，则用变量 res 记录遍历过程中子数组的最小长度，否则继续遍历。如果遍历结束后仍未找到，则返回 -1。但是在 LeetCode 上提交时会出现“超出时间限制”的提示！这说明该方法（时间复杂度为 O(n²)）还需优化，具体优化方法见思路 2。

（2）前缀和 & 双端队列
思路参考本题官方题解。

3.代码实现（Java）

//思路1————前缀和
class Solution {public int shortestSubarray(int[] nums, int k) {int res = Integer.MAX_VALUE;int length = nums.length;int[] preSum = new int[length + 1];for (int i = 1; i < length + 1; i++) {preSum[i] = preSum[i - 1] + nums[i - 1];//如果某个元素大于等于 k，那么满足条件的最短子数组的长度必为 1if (nums[i - 1] >= k) {return 1;}}for (int i = 0; i < length + 1; i++) {for (int j = i + 1; j < length + 1; j++) {// preSum[j] - preSum[i] 为数组 nums 中连续子数组[i, j)的和if (preSum[j] - preSum[i] >= k) {res = Math.min(res, j - i);/*由于子数组 nums[i...j - 1] 的和已经大于等于 k，且在第 2 层 for 循环中，i 的值固定，无需扩大 j 去判断以 nums[i] 开头的子数组的和，所以此处可以直接退出当前第 2 层循环，不过依然不能从根本上解决问题，在 LeetCode 上提交时会出现“超出时间限制”的提示！*/break;}}}//如果不存在满足条件的数组，返回 -1return res == Integer.MAX_VALUE ? -1 : res;}
}

//思路2————前缀和 & 双端队列
class Solution {public int shortestSubarray(int[] nums, int k) {int res = Integer.MAX_VALUE;int length = nums.length;long[] preSum = new long[length + 1];for (int i = 1; i < length + 1; i++) {preSum[i] = preSum[i - 1] + (long) nums[i - 1];if (nums[i - 1] >= k) {return 1;}}//定义双端队列Deque<Integer> deque = new ArrayDeque<>();for (int i = 0; i < preSum.length; i++) {while (!deque.isEmpty() && preSum[i] <= preSum[deque.getLast()]) {deque.removeLast();}while (!deque.isEmpty() && preSum[i] - preSum[deque.peek()] >= k) {res = Math.min(res, i - deque.poll());}deque.add(i);}return res == Integer.MAX_VALUE ? -1 : res;}
}