题目简介

*描述: *

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

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

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

实例：

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

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

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

输出：3

思路

思路1

​ 第一种当然就是直接暴力搜索，不过这样的话，复杂度会直接上升到O(n*n)，但是可以通过90%的样例

​ 代码就不写了，理解就OK

思路2

错误想法

​ 除了暴力搜索的方案之外，我还想到，用两个指针同向而行，这两个指针之间确定了一个子数组，先移动右指针，每当满足条件，我们就试着移动左指针，到条件不满足就停止，就好像一个 滑动窗口 一样，但是这个做法其实是错误的！

​ 比如测试样例为 [1,-100,1,2] 3，如果按上述方法来做，会找不到答案。原因在于，你无法确定这两个指针当中，是否存在有符合条件的窗口

继续思考

​ 我们每遍历到数组当中的一个位置，往回看怎样才能清楚前面哪个区间是符合条件的呢？把前面的位置再重新遍历一遍？那这就又回到了我们前面的暴力方法，肯定不是。

​ 换句话说我们要根据条件考虑前面的位置，这个考虑是在遍历的时候就考虑，而不用我们从头再去重复劳动，一开始我想到了队列，但是这个其实不准确，严格来说是 单调双端队列，也就是说这个队列头尾都可以出，而且里面存的元素是单调递增或者递减的，这有个什么好处呢？

​ 想法的核心在于：假如说我们当前考虑位置 i，这时区间 [0, i] 的值比区间 [0, i - 1] 的还要小，那么对于后面的位置，我们其实就不需要考虑了 i - 1 了，因为位置 sum[n] - sum[i] > sum[n] - sum[i - 1]，而且就长度来说的话 [i, n] 比 [i - 1, n] 更短，因此我们可以把 i - 1 这个位置踢出队列。

​ 换句话说，也就是如果数组里面都是正数，那么长度越长，区间和肯定越大，则 sums[i] 一定大于所有双向队列中的区间和，但由于可能存在负数，从而使得长度变长，区间总和反而减少了，所以如果出现上面这种情况直接将 i - 1 这个位置踢出队列即可。

​ 我们从队列中最小的位置开始计算，如果符合条件，我们就记录答案，并将这个位置踢出队列，道理很简单，再往后遍历不可能会有比这个还要小的符合条件的长度。

代码

代码1

这是我自己写的代码，调了我一整个上午，用数组来进行实现，最终通过。

但是还是麻烦了一点，尽管内存消耗少于100%的代码【骄傲.jpg

class Solution {
public:
    int shortestSubarray(vector<int>& A, int K) {
        vector<int> add;
        int a[50005];
        int head, tail;
        int min=-1;
        int temp_min=-1;
        head = tail = 0;
        memset(a, 0, sizeof(a));
        int cnt=0;
        int sum=0;
        while (sum < K && cnt<A.size())
            sum += A[cnt++];
        if (sum >= K)
            temp_min = cnt;
        add.push_back(A[0]);
        for (int i=1; i<A.size(); i++)
            add.push_back(A[i]+add[i-1]);
        for (int i=1; i<add.size(); i++){
            while (head<=tail && add[a[tail]]>=add[i] && a[tail]<=i)
                tail--;
            a[++tail] = i;
            while (add[a[head]]>=add[a[head+1]] && a[head]<a[head+1] && head<tail)
                head++;
            while (add[a[tail]] - add[a[head]] >= K && head<tail && add[a[tail]] - add[a[head+1]] >= K)
                head++;
            if (add[a[tail]] - add[a[head]] >= K){
                if (min > 0){
                    if (a[tail]-a[head] < min)
                        min = a[tail] - a[head];
                }
                else
                    min = a[tail] - a[head];
            }
        }
        if (min==-1 && temp_min!=-1)
            return temp_min;
        if (min!=-1 && temp_min!=-1 && temp_min<min)
            return temp_min;
        return min;
    }
};

代码2

嗯，我找了一下，这份代码比我的就简单很多了，赶紧学习一个！

没想到能直接用deque（我都不知道这东西【太菜了.jpg

class Solution {
public:
    int shortestSubarray(vector<int>& A, int K) {
        int sum[50005];
        int ret = 2e9;
        int n = A.size();
        for(int i = 0; i < n; i++) {
            sum[i+1] = sum[i] + A[i];
        }
        deque<int>que;
        que.push_back(0);
        for(int i = 1; i <= n; i++) {
            while(que.size() and sum[i] <= sum[que.back()])
                que.pop_back();
            while(que.size() and sum[i] - sum[que.front()] >= K) {
                ret = min(ret, i - que.front());
                que.pop_front();
            }
            
            que.push_back(i);
        }
        if(ret == 2e9) ret = -1;
        return ret;
    }
};

代码3

这个就更厉害了，赶紧膜一下！

static auto __ = [](){
    ios::sync_with_stdio(false);
    cin.tie(0);
    return 0;
}();

class Solution {
public:
    int shortestSubarray(vector<int>& A, int K) {
        int len = A.size();
        int sum = 0, begin = 0, res = -1;
        for (int i = 0; i < len; i++) {
            if (A[i] >= K) return 1;
            sum += A[i];
            if (sum < 1) {
                sum = 0;
                begin = i + 1;
                continue;
            }
            for (int j = i - 1; A[j + 1] < 0; j--) {
                A[j] = A[j + 1] + A[j];
                A[j + 1] = 0;
            }
            if (sum >= K) {
                while (sum - A[begin] >= K || A[begin] <= 0)
                    sum -= A[begin++];
                int length = i - begin + 1;
                if (res < 0 || res > length)
                    res = length;
            }
        }
        return res;
    }
};