题目描述

返回 A 的最短的非空连续子数组的长度，该子数组的和至少为 K 。

如果没有和至少为 K 的非空子数组，返回 -1

示例

输入：A = [1], K = 1
输出：1

输入：A = [1,2], K = 4
输出：-1

输入：A = [2,-1,2], K = 3
输出：3

提示

1. 1 <= A.length <= 50000
2. -10 ^ 5 <= A[i] <= 10 ^ 5
3. 1 <= K <= 10 ^ 9

首先对于我这样一个不怎么有基础的人来说，这道题着实是令我作呕。。解题也是通过了其它题解的启发。下面就开始吧。

解题想法

由于题目中已经明确表示了数组的长度为50000，因此如果要使用暴力接法，势必造成O(n^2)的时间复杂度。因此就要想办法让i， j两个循环变量只跑一遍。而对于这道题因为绕不开要求取数组中的区间和。所以可以采用的一个方法是前缀和思想。大致的意思就是sum[i] = array[0] + array[1] + … + array[i - 1]利用这个前缀和数组就可以较为方便的得到一个数组的区间和，例如要知道区间[1, 3]的和，我们可以利用前缀和数组得到sum[4] - sum[1]（这里需要注意的是，为了便于计算前缀和数组的第零个元素默认为零）

解决了前缀和之后就要解决更加关键的问题，如何能够得到最短长度的和最小序列。首先我们不妨先这么想，如果我们当前的索引为i， 此时若区间[0, i]的和比区间[0, i - 1]的和要小，那么就不需要再考虑i - 1这个位置的索引了（因为这个时候有sum[A.length] - sum[i] > sum[A.length] - sum[i - 1] 且前者的区间长度要小于后者）而这个时候就要原先的存储的i - 1这个索引弹出，再将更优的i索引加入。这个时候可以利用队列这样的数据结构来保存。有了这个存删的机制就可以保证每次能够得到的长度都是最短且和最大的。之后就是获得长度的问题了。如果这个队列中还有元素的话，就从当前遍历到的索引i的前缀和减去队列头部保存的索引，即（sum[i] - sum[queue.front()]）这个条件需要满足题目中给出的K。由此可以看出这个队列需要两端都能出，因此我们需要维护一个单调递增的双端队列。下面附上C++代码

class Solution {
public:
    int shortestSubarray(vector<int>& vec, int threshold) {
        int len = vec.size();
        int minLength = 5e4 + 11;
        deque<int> dque;
        vector<int> sum(len + 1, 0);  // 初始化前缀和数组
        for (int i = 1; i <= len; ++i) {
            sum[i] = sum[i - 1] + vec[i - 1];
        }
        for (int i = 0; i < len + 1; ++i) {
            if (i != 0) {
                // 满足性质就将队列尾部的索引给删除不再考虑
                while (dque.size() && sum[dque.back()] >= sum[i]) {
                    dque.pop_back();
                }
                // 从队列头部开始寻找满足条件的最短区间
                // 如果不满足条件就要将队列头部元素删除
                while (dque.size() && sum[i] - sum[dque.front()] >= threshold) {
                    minLength = min(minLength, i - dque.front());
                    dque.pop_front();
                }
            }
            dque.push_back(i);
        }
        return minLength == 5e4 + 11 ? -1 : minLength;
    }
};