[数据结构与算法]Leetcode刷题c++之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 <= 105
• -105?<= nums[i] <= 105
• 1 <= k <= 109

思路：

一开始我想到的方法就是暴力破解，直接用前缀和数组的方式来解决。

先求出前缀和数组prenums，要求出连续数组的和就是将前缀和数组中的后节点减去前节点，比如求i-j之内的连续数组和就是（prenums[j + 1] - prenums[i]）。然后通过双指针遍历前缀和数组，求出符合条件的连续数组，然后记录最短的子连续数组的长度。

代码如下：

class Solution {
public:
    vector<int> nums = {17,85,93,-45,-23};
    int k = 150;
    int shortestSubarray(vector<int>& nums, int k) {
        int length = nums.size();
        vector<long> prenums(length + 1);
        int flag = 0;
        int minlength = length;
        for (int i = 0; i < length; i++) {
            prenums[i + 1] = prenums[i] + nums[i];
        }
        for (int i = 0; i < length; i++) {
            for (int j = i; j < length; j++) {
                if (prenums[j + 1] - prenums[i] >= k) {
                    flag = 1;
                    minlength = min(j - i + 1, minlength);
                }
            }
        }
        if (flag == 1) {
            return minlength;
        }
        else
        {
            return -1;
        }
    }
};

但是这样的代码直接丢到力扣上跑，会超出时间限制，因为这样的算法里进行了双重循环，时间复杂度达到了O(n2)。

?所以我们必须对这个前缀和数组进行优化，将时间复杂度降下来。

优化一：

当我们遍历到prenums[j]时，考虑左边的某个prenums[i]，如果prenums[j] - prenums[i] >= k，那么无论prenums[j]右边的数字是大是小，都不可能把j当作子数组的左端点，得到一个比j-i更短的子数组了。所以prenums[j]就没用了，可以把他去掉。

优化二：

如果prenums[j] <= prenums[i],假如后续有数字x能和prenums[i]组成满足要求的子数组，即x-prenums[i] >= k,又因为prenums[j]比prenums[i]更小，而且离x更近，所以不需要prenums[i]了，可以把他去掉。

做完这两个优化后，再把prenums[j]加到这个数据结构中。

由于优化二保证了数据结构中的 prenums[j]会形成一个递增的序列，因此优化一移除的是序列最左侧的若干元素，优化二移除的是序列最右侧的若干元素。我们需要一个数据结构，它支持移除最左端的元素和最右端的元素，以及在最右端添加元素，故选用双端队列。

代码如下：

class Solution {
public:
    vector<int> nums = {17,85,93,-45,-23};
    int k = 150;
    int shortestSubarray(vector<int>& nums, int k) {
        int length = nums.size();
        vector<long> prenums(length + 1);
        prenums[0] = 0;
        int minlength = length + 1;
        for (int i = 0; i < length; i++) {
            prenums[i + 1] = prenums[i] + nums[i];
        }
        deque<int> q;
        for (int i = 0; i <= length; i++) {
            long cur_prenums = prenums[i];
            while (!q.empty() && cur_prenums - prenums[q.front()] >= k) {
                minlength = min(minlength, i - q.front());
                q.pop_front(); // 优化一
            }
            while (!q.empty() && prenums[q.back()] >= cur_prenums)
                q.pop_back(); // 优化二
            q.push_back(i);
        }
        return minlength > length ? -1 : minlength;
    }
};