【LeetCode每日一题】——862.和至少为 K 的最短子数组

文章目录

一【题目类别】
二【题目难度】
三【题目编号】
四【题目描述】
五【题目示例】
六【题目提示】
七【解题思路】
八【时空频度】
九【代码实现】
十【提交结果】

一【题目类别】

前缀和

二【题目难度】

困难

三【题目编号】

862.和至少为 K 的最短子数组

四【题目描述】

给你一个整数数组 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^5$
$10^5 <= nums[i] <= 10^5$
$1 <= k <= 10^9$

七【解题思路】

利用前缀和+双端队列解决该问题
前缀和数组（prefix_sum）用来存储原数组（nums）第i个位置的之前i-1个元素的和
双端队列（存储数组下标，并且是个递增的双端队列）来做两个优化：
- 优化左端：假设i > j，且prefix_sum[i] - prefix_sum[j] ≥ k，那么更新结果值（res）为其中小值，并且将i入双端队列，因为就算后面还有满足其差≥k的情况，其长度也不是最小的
- 优化右端：假设h > i > j，并且prefix_sum[i] <= 双端队列右端的值，那么将双端队列右端的值弹出，重复以上过程直到prefix_sum[i] > 双端队列右端的值，因为假设此时prefix_sum[j] >= prefix_sum[i]，所以不仅更难满足prefix_sum[h] - prefix_sum[j] ≥ k，并且h - i < h - j，所以需要将j弹出
当然，原数组的每个下标都要进入双端队列一次
最后返回结果即可
具体细节可以参考下面的代码

八【时空频度】

时间复杂度： $O (n)$ ， $n$ 为传入数组的长度
空间复杂度： $O (n)$ ， $n$ 为传入数组的长度

九【代码实现】

Java语言版

class Solution {
    public int shortestSubarray(int[] nums, int k) {
        // 初始化前缀和数组
        long[] prefix_sum = new long[nums.length + 1];
        prefix_sum[0] = 0;
        for (int i = 0; i < nums.length; i++) {
            prefix_sum[i + 1] = prefix_sum[i] + nums[i];
        }
        // 保存结果值
        int res = Integer.MAX_VALUE;
        // 初始化双端队列
        Deque<Integer> queue = new ArrayDeque<>();
        for (int i = 0; i < prefix_sum.length; i++) {
            // 优化左端：可以找到距离更短的子数组
            while (!queue.isEmpty() && prefix_sum[i] - prefix_sum[queue.peekFirst()] >= k) {
                res = Math.min(res, i - queue.pollFirst());
            }
            // 优化右端：大于当前子数组前缀和的之前的子数组前缀和没用了，无法构成满足条件下更短的子数组
            while (!queue.isEmpty() && prefix_sum[i] <= prefix_sum[queue.peekLast()]) {
                queue.pollLast();
            }
            // 将数组下标入双端队列
            queue.offerLast(i);
        }
        // 返回结果
        return res == Integer.MAX_VALUE ? -1 : res;
    }
}

Python语言版

class Solution:
    def shortestSubarray(self, nums: List[int], k: int) -> int:
        # 初始化前缀和数组
        prefix_sum = [0]
        for num in nums:
            prefix_sum.append(prefix_sum[-1] + num)
        # 保存结果值
        res = inf
        # 初始化双端队列
        queue = deque()
        for i, prefix_num in enumerate(prefix_sum):
            # 优化左端：可以找到距离更短的子数组
            while queue and prefix_num - prefix_sum[queue[0]] >= k:
                res = min(res, i - queue.popleft())
            # 优化右端：大于当前子数组前缀和的之前的子数组前缀和没用了，无法构成满足条件下更短的子数组
            while queue and prefix_sum[queue[-1]] >= prefix_num:
                queue.pop()
            # 将数组下标入双端队列
            queue.append(i)
        # 返回结果
        return res if res < inf else -1

C++语言版

class Solution {
public:
    int shortestSubarray(vector<int>& nums, int k) {
        // 初始化前缀和数组
        std::vector<long long> prefix_sum(nums.size() + 1, 0);
        for (int i = 0; i < nums.size(); i++) {
            prefix_sum[i + 1] = prefix_sum[i] + nums[i];
        }
        // 保存结果值
        int res = INT_MAX;
        // 初始化双端队列
        std::deque<int> queue;
        for (int i = 0; i < prefix_sum.size(); i++) {
            // 优化左端：可以找到距离更短的子数组
            while (!queue.empty() && prefix_sum[i] - prefix_sum[queue.front()] >= k) {
                res = std::min(res, i - queue.front());
                queue.pop_front();
            }
            // 优化右端：大于当前子数组前缀和的之前的子数组前缀和没用了，无法构成满足条件下更短的子数组
            while (!queue.empty() && prefix_sum[i] <= prefix_sum[queue.back()]) {
                queue.pop_back();
            }
            // 将数组下标入双端队列
            queue.push_back(i);
        }
        // 返回结果
        return res == INT_MAX ? -1 : res;
    }
};