LeetCode_前缀和_困难_862.和至少为 K 的最短子数组

偏执的太偏执、 2023-10-06 23:22 84阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 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 <= 105  
\-105 <= nums\[i\] <= 105  
1 <= k <= 109

来源：力扣（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(n2)）还需优化，具体优化方法见思路 2。**

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

## 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，那么满足条件的最短子数组的长度必为 1
                if (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;
                    }
                }
            }
            //如果不存在满足条件的数组，返回 -1
            return 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;
        }
    }

[Link 1]: https://leetcode.cn/problems/shortest-subarray-with-sum-at-least-k/solution/he-zhi-shao-wei-k-de-zui-duan-zi-shu-zu-by-leetcod/