个人中心
gpt4 book ai didi

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

转载 作者：知者 更新时间：2024-03-12 12:37:35 29 4
gpt4 key购买 nike

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）前缀和 & 双端队列
思路参考本题官方题解。

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;
    }
}

29 4 0
文章推荐： 要想不踩SaaS那些坑，得先了解“SaaS架构”
文章推荐： 抖音白天与晚上触发不同特效的Graph节点编写
文章推荐： VUE学习笔记详细
文章推荐： 三种缓存策略：Cache Aside 策略、Read/Write Through 策略、Write Back 策略
知者
个人简介

我是一名优秀的程序员,十分优秀！

滴滴打车优惠券免费领取
滴滴打车优惠券
全站热门文章
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com