LeetCode 862 - Shortest Subarray with Sum at Least K

https://leetcode.com/problems/shortest-subarray-with-sum-at-least-k/

Return the length of the shortest, non-empty, contiguous subarray of A with sum at least K.

If there is no non-empty subarray with sum at least K, return -1.

Example 1:

Input: A = [1], K = 1
Output: 1

Example 2:

Input: A = [1,2], K = 4
Output: -1

Example 3:

Input: A = [2,-1,2], K = 3
Output: 3

Note:

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

X.
http://ryansiroiro.blogspot.com/2018/07/leetcode-862-shortest-subarray-with-sum.html
This problem remind us of a very similar problem: find the maximum subarray of an array. There are a couple of algorithms that can solve the maximum subarray problem efficiently. One of the solution is the following: we first calculate the prefix sum array S of array A(e.g. $S_i={\sum }_{j=1}^i{A}_j$). When we scan the array S from left to right, we keep track of the minimum value we've seen so far. Let minValue denote the current minimum value. It follows that S[i] - minValue is a potential candidates and we simple update the result by result = max(result, S[i] - minValue).

We make two observations here: (1) this algorithm is incremental. When we are at the index i, we will have the maximum subarray of A[0,...,i] and then we move to i+1 (2) subtract the minimum value that we have seen so far is a greedy guess. It is the optimal choice when we are at index i.

If we apply the same strategies here, a natural question is what the best guess would be. Imagine we are at index i. We can of course calculate each $S_i-S_j$ with $j<i$ and compare the value to K. If it is greater than K, we can then update the value of the optimal length. This approach gives us a $O\left(N^2\right)$ solution. This is a brute force approach and we do not make any guess.

We can do better. It turns out that we do not need to try each j that is less than i. Think of $S_m$ and $S_n$ with $m<n<i$. If $S_m\ge S_n$, we know for sure that $S_m$ is a worse candidate to be subtract than $S_n$ because $S_i-S_m\le S_i-S_n$ and $i-m>i-n$. In other word, the subarray $A[n,n+1,...,i]$ is always a better solution than $A[m,m+1,...,i]$.

Therefore, we only need to maintain a sequence of $(j,S_j)$ and more importantly, $S_j$ is increasing. Each time we are at an index i, we will find the index j such that $j<i$ and $S_i-S_j\ge K$. We then update the the value of the optimal length and add the pair $(i,S_i)$ to the sequence while maintaining its property. Following this approach, we will have a $O\left(NlogN\right)$ solution. The $logN$ part comes from the search part.

We can improve the algorithm further. Again, assume we are at index i. We also assume that we find a j such that $j<i$and $S_i-S_j\ge K$. Now the question is do we need to keep $(j,S_j)$ in the sequence? It turns out that we actually don't. The reason is that $S_j$ will never be used any more. Imagine that we will be at an index i' later with $i^{\prime }>i$. Even if $S_i^{\prime }-S_j\ge K$, we will always have a longer subarray of $A[j,j+1,...i^{\prime }]$.
http://hehejun.blogspot.com/2018/07/leetcodeshortest-subarray-with-sum-at.html
首先这道题没有办法用普通的双指针做，因为随着首尾两个指针的移动，子数组的和不是单调地变化的，所以我们没有办法每次移动右边的指针之后再移动左边的指针找到size最小的subarray。类似地，binary search之类的做法也是不行的，比如我们验证存不存在长度为i的子数组和大于等于K，假如不存在的话，我们没有办法决定是增大下界还是缩小上界，因为长度更小的subarray的和可能更大。所以我们要思考其他的方法，我们可以观察出几个特点：

1. presum[i]表示从0到i的前缀和，如果对于i < j，presum[i] >= presum[j]的情况，显然对于j之后的index k。如果presum[k] - presum[i]大于等于K，那么因为presum[k] - presum[j] >= presum[k] - presum[i]，所以presum[k] - presum[j]必定也满足条件而且[j + 1, k]这个区间比[i + 1, k]更短
2. 对于j > i，如果j是满足presum[j] - presum[i] >= K的最小值。那么对于k > j，我们不需要考虑presum[k] - presum[i]了，因为即使区间和大于K也比[i +1, j]要长

所以这给了我们一个类似于Sliding Window Maximum的思路，如果我们维护一个递增的前缀和的序列s，对于我们所在的当前index i:

1. 如果这个序列的尾巴对应前缀和s.back() >= presum[i]，我们pop_back()。对应上面的情况1，我们不需要考虑其作为区间起始位置的情况，因为i是永远比它更优的起始位置。
2. 如果这个序列的头对应的前缀和满足presum[i] - s.front() >= K，pop_front()，更新最小区间，对应情况2。已经pop出来的都将其作为区间起始位置考虑过并且存在某个以其为起始的区间大于等于K，还在序列s之中的都是其作为区间开头不满足在扫过的index中存在某个以它开始的区间，其区间和大于等于K。

同时需要在序列的头和尾进行pop的操作，我们选择deque来实现。时间复杂度为O(n)，显而易见每个元素进出队列一次，空间复杂度O(n)。

https://www.gjxhlan.me/2018/07/07/leetcode-contest-91-solution/

我一直觉得 Deque 和二分一直是解题中两个比较美妙的解法，两者分别有着 O(n) 和 O(logn) 的潜力。

这道题可以用 Deque 做。

设数组 B[i] 存储的是 1 ~ i 的子序和，Deque<Integer> q 保存的是一个 index 序列，使得 B[q[j]] < B[q[k]] if j < k in q。

当我们遍历到 i 时，求得 B[i] ，从 Deque 的 tail 处往前遍历，如果 B[q[tail]] > B[i]，那么之后的任意一段子数组和 K <= B[j] - B[q[tail]] < B[j] - B[i] ，即 q[tail] ~ j 的解不会优于当前解i ~ j，所以可以放心的将其弹出。

再从 Deque 的头部往后遍历，如果当前 B[i] - B[q[front]] >= K 满足解的条件，那么对之后任意 j > i 其子数组的长度都不会比 i - q[front] 短，所以我们也可以放心地将其弹出。

所有的元素只会进入一次 Deque 并被弹出一次，所以时间复杂度为 O(n)。

https://blog.csdn.net/yanglingwell/article/details/80875790
滑动窗口（O(n)）

实际上，当 frontSum[j]-frontSum[i-1] <= 0， 即表示 i 到 j 的元素和小于等于零，会成为后面的负担（增加长度，却不增加和）。因此，j 后面的元素计算最小长度时，可以不用考虑 i 到 j 这一段。

  int shortestSubarray(vector<int>& A, int K) {

    vector<long long int> frontSum(A.size()+1, 0);

    for(int i = 1; i <= A.size(); ++i)

    {

        frontSum[i] = frontSum[i-1] + A[i-1];

    }

    int ans = -1;

    deque<int> begCandidates; 

    // 每一次循环处理： 以 end 为结束的 Shortest Subarray with Sum at Least K

    for(size_t end = 0; end <= A.size(); ++end)

    {

        // 如果 begCandidates.back() 到 end 的和是负的，

        // 则计算 end 之后的 “以 end 为结束的 Shortest Subarray with Sum at Least K”， 

        // 不再需要从 begCandidates.back() 开头子数组

        while(!begCandidates.empty() && frontSum[end] - frontSum[begCandidates.back()] <= 0)

        {

            begCandidates.pop_back();

        }

        // 如果 begCandidates.front() 到 end 的和大于等于 K， 则其可能是备选方案

        while(!begCandidates.empty() && frontSum[end] - frontSum[begCandidates.front()] >= K)

        {

            // 如果 begCandidates.front() 到 end 的和大于等于 K, 

            // 则后面的计算不再需要 begCandidates.front() 

            // 因为，begCandidates.front()为起始，和大于等于 K 的，

            // 最小距离一定小于等于 end - begCandidates.front()。

            int beg = begCandidates.front();

            begCandidates.pop_front();

            if(ans == -1) ans = end - beg;

            else ans = min(ans, (int)end - beg);

        }

        begCandidates.push_back(end);

    }

    return ans;

  }

https://leetcode.com/problems/shortest-subarray-with-sum-at-least-k/discuss/143726/C%2B%2BJavaPython-O(N)-Using-Deque

Calculate prefix sum B of list A.
B[j] - B[i] represents the sum of subarray A[i] ~ A[j-1]
Deque d will keep indexes of increasing B[i].
For every B[i], we will compare B[i] - B[d[0]] with K.

Q: How to think of such solutions?
A: Basic idea, for array starting at every A[i], find the shortest one with sum at leat K.
In my solution, for B[i], find the smallest j that B[j] - B[i] >= K.
Keep this in mind for understanding two while loops.

Q: What is the purpose of first while loop?
A: For the current prefix sum B[i], it covers all subarray ending at A[i-1].
We want know if there is a subarray, which starts from an index, ends at A[i-1] and has at least sum K.
So we start to compare B[i] with the smallest prefix sum in our deque, which is B[D[0]], hoping that [i] - B[d[0]] >= K.
So if B[i] - B[d[0]] >= K, we can update our result res = min(res, i - d.popleft()).
The while loop helps compare one by one, until this condition isn't valid anymore.

Q: Why we pop left in the first while loop?
A: This the most tricky part that improve my solution to get only O(N).
D[0] exists in our deque, it means that before B[i], we didn't find a subarray whose sum at least K.
B[i] is the first prefix sum that valid this condition.
In other words, A[D[0]] ~ A[i-1] is the shortest subarray starting at A[D[0]] with sum at least K.
We have already find it for A[D[0]] and it can't be shorter, so we can drop it from our deque.

Q: What is the purpose of second while loop?
A: To keep B[D[i]] increasing in the deque.

Q: Why keep the deque increase?
A: If B[i] <= B[d.back()] and moreover we already know that i > d.back(), it means that compared with d.back(),
B[i] can help us make the subarray length shorter and sum bigger. So no need to keep d.back() in our deque.

https://leetcode.com/problems/shortest-subarray-with-sum-at-least-k/discuss/189039/Detailed-intuition-behind-Deque-solution

What makes this problem hard is that we have negative values. If you haven't already done the problem with positive integers only, I highly recommend solving it first, as we will use its Sliding Window solution to reach the Deque solution here. You can find the problem here : https://leetcode.com/problems/minimum-size-subarray-sum/description/ , and a Sliding window solution here : https://leetcode.com/problems/minimum-size-subarray-sum/discuss/59078/Accepted-clean-Java-O(n)-solution-(two-pointers).

Recall of the Sliding window solution in a positive array

The Sliding window solution finds the subarray we are looking for in a linear time complexity. The idea behind it is to maintain two pointers: start and end, moving them in a smart way to avoid examining all possible values 0<=end<=n-1 and 0<=start<=end (to avoid brute force).
What it does is:

1. Incremeting the end pointer while the sum of current subarray (defined by current values of start and end) is smaller than the target.
2. Once we satisfy our condition (the sum of current subarray >= target) we keep incrementing the start pointer until we violate it (until sum(array[start:end+1]) < target).
3. Once we violate the condition we keep incrementing the end pointer until the condition is satisfied again and so on.

The reason why we stop incrementing start when we violate the condition is that we are sure we will not satisfy it again if we keep incrementing start. In other words, if the sum of the current subarray start -> end is smaller than the target then the sum of start+1 -> end is neccessarily smaller than the target. (positive values)
The problem with this solution is that it doesn't work if we have negative values, this is because of the sentence above Once we "violate" the condition we stop incrementing start.

Problem of the Sliding window with negative values

Now, let's take an example with negative values nums = [3, -2, 5] and target=4. Initially start=0, we keep moving the end pointer until we satisfy the condition, here we will have start=0 and end=2. Now we are going to move the start pointer start=1. The sum of the current subarray is -2+5=3 < 4 so we violate the condition. However if we just move the start pointer another time start=2 we will find 5 >= 4 and we are satisfying the condition. And this is not what the Sliding window assumes.

What does the Deque store :
The deque stores the possible values of the start pointer. Unlike the sliding window, values of the start variable will not necessarily be contiguous.

Why is it increasing :
So that when we move the start pointer and we violate the condition, we are sure we will violate it if we keep taking the other values from the Deque. In other words, if the sum of the subarray from start=first value in the deque to end is smaller than target, then the sum of the subarray from start=second value in the deque to end is necessarily smaller than target.
So because the Deque is increasing (B[d[0]] <= B[d[1]]), we have B[i] - B[d[0]] >= B[i] - B[d[1]], which means the sum of the subarray starting from d[0] is greater than the sum of the sub array starting from d[1].

Why are we having a prefix array and not just the initial array like in the sliding window :
Because in the sliding window when we move start (typically when we increment it) we can just substract nums[start-1] from the current sum and we get the sum of the new subarray. Here the value of the start is jumping and the only way to compute the sum of the current subarray in a constant time is to have the prefix array.

https://ttzztt.gitbooks.io/lc/content/combination/shortest-subarray-with-sum-at-least-k.html

    public int shortestSubarray(int[] A, int K) {
        int N = A.length, res = N + 1;
        int[] S  = new int[N+ 1];
        for(int i = 0; i < N; i++) S[i + 1] = S[i] + A[i];
        Deque<Integer> d = new LinkedList();
        for(int i = 0; i < N + 1; i++){
            while(d.size() > 0 && S[i] - S[d.peekFirst()] >= K){
                res = Math.min(res, i - d.pollFirst()); 
            }
            // keep the INCREASING order to keep the optimal result (index larger should have larger(equal) value in the queue)
            while(d.size() > 0 && S[i] <= S[d.peekLast()]){
                d.pollLast();
            }
            d.offerLast(i);
        }

        return res == N + 1? -1: res;
    }

https://blog.csdn.net/u012525096/article/details/81531731
（2）opt(i,k)：长度为i的数组，找和至少为k的连读子数组的长度。opt(i,k)=min{1+opt(i-1,k-A[i]), opt(i-1,K)}，结果是失败的，要连续；故写成两种递归，若选了该值，后面都要选，不然不连续；修改后，还是超时，这是自上而下，且没用辅助数组存储结果，但是想想好像没法存，是两个变量（i和k）控制，可能重叠的问题太少了。

官方解答：
（1）P[i] 是前i项的和，任何一段连续子数组都可以通过P[y] - P[x] 得到。
（2）目标opt(y) : P[x]<=P[y]-K，找最小的x。
考虑两种情况：
1）若x1<x2，且P[x1]>=P[x2]，则最终的结果肯定选的是x2，因为选了x2，让子串长度更短。
P[x1]<=P[y]-K,P[x2]<=P[y]-K，选x2。
2）若P[x]<=P[y1]-K,P[x]<=P[y2]-K，且y1

  public static int shortestSubarray(int[] A, int K) {

    int N = A.length;

    long[] P = new long[N + 1];

    for (int i = 0; i < N; ++i)

      P[i + 1] = P[i] + (long) A[i];

    // Want smallest y-x with P[y] - P[x] >= K

    int ans = N + 1; // N+1 is impossible

    Deque<Integer> monoq = new LinkedList<>(); // opt(y) candidates, as indices of P

    for (int y = 0; y < P.length; ++y) {

      // Want opt(y) = largest x with P[x] <= P[y] - K;

      // 如果P[x1]P[x2]都进去,那么一定选的是P[x2],而不会选P[x1],所以P[x1]直接弹出去

      while (!monoq.isEmpty() && P[y] <= P[monoq.getLast()])

        monoq.removeLast();

      // 判断和队首元素相减,是不是大于等于K,是的话求一下长度,比较一下

      // 弹出队首,因为已经是最短的了,后面的P[y]若满足,也是更长的

      while (!monoq.isEmpty() && P[y] >= P[monoq.getFirst()] + K)

        ans = Math.min(ans, y - monoq.removeFirst());

      monoq.addLast(y);

    }

    return ans < N + 1 ? ans : -1;

  }

https://www.cnblogs.com/f91og/p/9494922.html

上面的出入队列顺序是这样的：首先对于每个索引i，对应的是B[i]，将这个索引作为y位置来考虑，因为双端队列保持的索引是的B[i]是递增的，为了从最大处逼近K，我们从队头依次取索引出来计算：

B[i] - B[d.getFirst()]

如果比K大，那么则要找这其中距离索引i最近的那一个：

res = Math.min(res, i - d.pollFirst());

然后是队列要keep indexes of increasing B[i]，索引判断当前的B[i]是否大于队列尾部的索引处的

B[i] <= B[d.getLast()

如果不能构成递增，根据之前的分析，当前y所在的位置i的最优解opt(y)一定不会是在前面递增的部分取，所以队列要从后往前一个个弹出队尾直至能和B[i]构成递增序列。

https://leetcode.com/articles/shortest-subarray-with-sum-atleast-k/

We can rephrase this as a problem about the prefix sums of A. Let P[i] = A[0] + A[1] + ... + A[i-1]. We want the smallest y-x such that y > x and P[y] - P[x] >= K.

Motivated by that equation, let opt(y) be the largest x such that P[x] <= P[y] - K. We need two key observations:

• If x1 < x2 and P[x2] <= P[x1], then opt(y) can never be x1, as if P[x1] <= P[y] - K, then P[x2] <= P[x1] <= P[y] - K but y - x2 is smaller. This implies that our candidates x for opt(y) will have increasing values of P[x].
• If opt(y1) = x, then we do not need to consider this x again. For if we find some y2 > y1 with opt(y2) = x, then it represents an answer of y2 - x which is worse (larger) than y1 - x.

Algorithm

Maintain a "monoqueue" of indices of P: a deque of indices x_0, x_1, ... such that P[x_0], P[x_1], ... is increasing.

When adding a new index y, we'll pop x_i from the end of the deque so that P[x_0], P[x_1], ..., P[y] will be increasing.

If P[y] >= P[x_0] + K, then (as previously described), we don't need to consider this x_0 again, and we can pop it from the front of the deque.

  public int shortestSubarray(int[] A, int K) {

    int N = A.length;

    long[] P = new long[N + 1];

    for (int i = 0; i < N; ++i)

      P[i + 1] = P[i] + (long) A[i];

    // Want smallest y-x with P[y] - P[x] >= K

    int ans = N + 1; // N+1 is impossible

    Deque<Integer> monoq = new LinkedList(); // opt(y) candidates, as indices of P

    for (int y = 0; y < P.length; ++y) {

      // Want opt(y) = largest x with P[x] <= P[y] - K;

      while (!monoq.isEmpty() && P[y] <= P[monoq.getLast()])

        monoq.removeLast();

      while (!monoq.isEmpty() && P[y] >= P[monoq.getFirst()] + K)

        ans = Math.min(ans, y - monoq.removeFirst());

      monoq.addLast(y);

    }

    return ans < N + 1 ? ans : -1;

  }

X.
https://www.acwing.com/solution/leetcode/content/612/
(树状数组) O(nlogn)O(nlog⁡n)
构造前缀和数组 s(i)s(i)，对于每个 ii，找到最大的 j<ij<i，使得 s(j)+K≤s(i)s(j)+K≤s(i)，则以 ii 结尾的最小的答案就是 i−ji−j。
将所有 0,s(i),K,s(i)+K0,s(i),K,s(i)+K 进行离散化，离散化到 [1,2n+2][1,2n+2]，然后使用树状数组寻找最大的 jj。
具体地，每次从树状数组中寻找一个前缀最大值，然后再更新树状数组即可。
时间复杂度
每次更新和查询的时间复杂度为 O(logn)O(log⁡n)，故总时间复杂度为 O(nlogn)O(nlog⁡n)。

  void update(vector<int> &f, int x, int y) {

    for (; x < f.size(); x += x & -x)

        f[x] = max(f[x], y);

}

int query(vector<int> &f, int x) {

    int t = -1;

    for (; x; x -= x & -x)

        t = max(f[x], t);

    return t;

}

int shortestSubarray(vector<int>& A, int K) {

    int n = A.size();

    vector<int> s(2 * n + 2, 0), d(2 * n + 2, 0);

    vector<int> f(2 * n + 3, -1);

    for (int i = 1; i <= n; i++) {

        s[i] = s[i - 1] + A[i - 1];

        d[i] = s[i];

    }

    for (int i = n + 1; i <= 2 * n + 1; i++) {

        s[i] = s[i - n - 1] + K;

        d[i] = s[i];

    }

    sort(d.begin(), d.end());

    for (int i = 0; i <= 2 * n + 1; i++)

        s[i] = lower_bound(d.begin(), d.end(), s[i]) - d.begin() + 1;

    update(f, s[n + 1], 0);

    int ans = n + 1;

    for (int i = 1; i <= n; i++) {

        int t = query(f, s[i]);

        if (t != -1)

            ans = min(ans, i - t);

        update(f, s[i + n + 1], i);

    }

    if (ans == n + 1)

        ans = -1;

    return ans;

}

X. TreeMap
https://leetcode.com/problems/shortest-subarray-with-sum-at-least-k/discuss/143746/Simple-Java-Solution-Using-TreeMap

Why we can remove entries from map
The reason we remove entries from preSum map is that:
for ith element, we find an element in preSum. Let's say starting from j. array[j - i] is the shortest subarray we can get for subarray starting from j, because we will move to i + 1 in the next iteration. And before i, we didn't find a solution for jth element, otherwise j would have already been removed.
Time complexity
Since treeMap keeps removing satisfactory entries, it can take O(nlogn) for while loop. But it removes entry. We will only go through N entries once in the for loop. I think worst case is O(nlogn).

    public int shortestSubarray(int[] A, int K) {
        TreeMap<Integer, Integer> preSum = new TreeMap<>();
        preSum.put(0, -1);
        int minLen = Integer.MAX_VALUE;
        int curSum = 0;
        for (int i = 0; i < A.length; i++) {
            curSum += A[i];
            Map.Entry<Integer, Integer> entry = preSum.floorEntry(curSum - K);
            while (entry != null) {
                int key = entry.getKey();
                minLen = Math.min(minLen, i - entry.getValue());    //here i - value of map not key!
                preSum.remove(key);
                entry = preSum.floorEntry(key);
            }
            preSum.put(curSum, i);
        }
        return (minLen == Integer.MAX_VALUE) ? -1 : minLen;
    }

https://leetcode.com/problems/shortest-subarray-with-sum-at-least-k/discuss/143746/Simple-Java-Solution-Using-TreeMap
https://ttzztt.gitbooks.io/lc/content/combination/shortest-subarray-with-sum-at-least-k.html

   public int shortestSubarray(int[] A, int K) {
        if (A.length == 0) return -1;
        TreeMap<Long, Integer> map = new TreeMap();
        map.put(0L, -1); // pay attention to the initial state
        long cumSum = 0; // sum of range[0-->i]
        int minLen = Integer.MAX_VALUE;
        for (int i = 0; i < A.length; i++) {
            // get cur cumSum
            cumSum += A[i];
            // find all candidates and update res (firstKey() will throw exception if map is empty)
            Long lowestKey = map.firstKey(), floorKey = map.floorKey(cumSum - K);
            if (lowestKey != null && floorKey != null) {
                Map<Long, Integer> subMap = new HashMap(map.subMap(lowestKey, true, floorKey, true));
                for (Long key: subMap.keySet()) {
                    int curLen = i - subMap.get(key);
                    if (minLen > curLen) minLen = curLen;  // update res
                    else map.remove(key);                  // prune bad candidate
                }
            }
            // put new cumSum to tree
            map.put(cumSum, i);
        }
        return minLen == Integer.MAX_VALUE ? -1 : minLen;
    }




TreeMap 的解法和 Deque 的思想是一致的，但是它需要维护 logn 的插入和 logn 的寻找弹出。其他的倒是没什么不同。

    public int shortestSubarray(int[] A, int K) {
        int ans = Integer.MAX_VALUE;
        TreeMap<Integer, Integer> map = new TreeMap<>();
        int sum = 0;
        map.put(0, -1);
        for (int i = 0; i < A.length; i++) {
            sum += A[i];
            Integer sub = map.floorKey(sum - K);
            while (sub != null) {
                ans = Math.min(ans, i - map.get(sub));
                map.remove(sub);
                sub = map.floorKey(sub);
            }
            map.put(sum, i);
        }
        
        return ans == Integer.MAX_VALUE ? -1 : ans;
    }

X. Bisection
https://ttzztt.gitbooks.io/lc/content/combination/shortest-subarray-with-sum-at-least-k.html

    public int shortestSubarray(int[] A, int K) {
        int N = A.length;

        // Compute cumulative sum
        int[] cumSum = new int[N];
        for (int i = 0; i < N; ++i) {
            cumSum[i] = i > 0 ? cumSum[i-1] + A[i] : A[i];
        }

        if (!existsSolution(cumSum, K, N)) return -1;

        // Binary search over all possible lengths
        int l = 1, r = N;
        while (l < r) {
            int m = l + (r-l) / 2;
            if (existsSolution(cumSum, K, m)) {
                r = m;
            } else {
                l = m+1;
            }
        }

        return l;
    }

    boolean existsSolution(int[] cumSum, int K, int len) {
        // Priority queue that maintains minimal value within the window of size 'len'
        PriorityQueue<VI> pq = new PriorityQueue<>((a, b) -> Integer.compare(a.val, b.val));
        pq.add(new VI(0, -1));

        for (int i = 0; i < cumSum.length; ++i) {
            // Clean up minimal elements that are outside of the window
            while (!pq.isEmpty() && pq.peek().pos < i-len) {
                pq.poll();
            }
            int windowMin = !pq.isEmpty() ? pq.peek().val : 0;
            if (cumSum[i] - windowMin >= K) {
                return true;
            } 
            pq.add(new VI(cumSum[i], i));
        }

        return false;
    }

    public static class VI {
        public int val, pos;

        public VI(int val, int pos) {
            this.val = val;
            this.pos = pos;
        }
    } 




X. Brute Force
https://blog.csdn.net/yanglingwell/article/details/80875790
朴素思想(O(n)^2, TLE)
记 ，前 x 数（包括第 x 个数）的和为 frontSum[x]， 则第 i 个数到第 j 个数的和为 frontSum[j]-frontSum[i-1]。 
遍历 i, j 的情况，求出和大于等于 K， 且长度最小的数组即可。复杂度 O(n^2)。

  int shortestSubarray(vector<int>& A, int K) {

    // 前序和

    vector<long long int> frontSum(A.size()+1, 0);

    for(int i = 1; i <= A.size(); ++i)

    {

        frontSum[i] = frontSum[i-1] + A[i-1];

    }

    int ans = -1;

    // 枚举所有情况

    for(int i = 0; i < A.size(); ++i)

    {

        for(int j = i; j < A.size(); ++j)

        {

            if(frontSum[j+1] - frontSum[i] >= K && (ans == -1 || ans > j+1-i))

            {

                ans = j+1-i;

                break;

            }

        }

    }

    return ans;

 }

X. https://www.codetd.com/article/2528681

    最开始我的思路用一把越来越大的尺子，每次从左往右移，只要有尺子在一个位置上的和大于等于K，那就直接返回当前尺子的长度，而且在计算尺子内的值的和时，可以先算出第一个位置上的和，之后往后移动的时候，每次加上新的值（right），减去旧的值（left - 1）。这样只要答案的长度不是太大，大循环（每次尺子长度+1）就不会循环太多次。

int shortestSubarray(vector<int>& A, int K)
{
    if(A.size() == 1)
        return A[0] >= K ? 1 : 0;
    bool isFind;
    for(int i = 0; i < A.size(); i++)   // 先看看每个数有没有
    {
        if(A[i] >= K)
        return 1;
    }
    for(int len = 1; len < A.size(); len++) // 每次循环用len长度的尺子从左往右走
    {
        int left = 0;
        int right = len;
        int cur_sum = 0;
        for(int t = left; t <= right; t++)
            cur_sum += A[t];
        if(cur_sum >= K)
            return len + 1;
        while(right  < A.size() - 1)
        {
            ++left;
            ++right;
            cur_sum += A[right];
            cur_sum -= A[left - 1];
                
            if(cur_sum >= K)
                return len + 1;
        }
    }
    return -1;
}

    思路以及答案没有问题，但是25万个数的时候，超时了，答案使用deque（有的使用priority_queue）来完成。大致思路是，计算每个位置上，加上后边多少位的数，能够大于等于K，找出最小的。

X. https://leetcode.com/problems/shortest-subarray-with-sum-at-least-k/discuss/151169/my-solution-O(nlgn)-use-segment-tree

1. calculate the prefix sum sum of A
2. build a segment tree to store the minimum of prefix sum
3. query the result
   sum[i] - sum[p] >= K
   we will find the max p that satisfy the condition and less than i, for each i, we can get a p, and the shortest subarray is i - p. (attention of corner case, if we can't find a p)

    struct node{
        int s,e;
        long long mi;
        node* left, *right;
        node(int s, int e, long long mi):s(s),e(e), mi(mi), left(0), right(0){}
        ~node(){
            if (left)delete left;
            if (right) delete right;
        }
    };
    node* build(vector<long long>& A, int l, int r){
        node* root=new node(l,r,A[l]);
        if (l==r) return root;
        root->left=build(A, l, (l+r)/2);
        root->right=build(A, (l+r)/2+1, r);
        root->mi=min(root->left->mi, root->right->mi);
        return root;
    }
    int query(node* root, int l, int r, int k){
        if (l>r) return -1;
        if (root->s>r||root->e<l||root->mi>k) return -1;
        if (root->s==root->e&&root->mi<=k) return root->s;
        int rr=query(root->right, l, r, k);
        if (rr==-1){
            return query(root->left, l, r, k);
        }
        return rr;
    }
public:
    int shortestSubarray(vector<int>& A, int K) {
        int n=A.size();
        vector<long long> sum(n);
        sum[0]=A[0];
        for (int i=1;i<n;++i) sum[i]=sum[i-1]+A[i];
        node* root=build(sum, 0, n-1);
        int ans=n+1;
        for (int i=0;i<n;++i){
            if (sum[i]>=K) ans=min(ans, i+1);
            int p=query(root, 0, i-1, sum[i]-K);//cout<<i<<ends<<p<<ends<<sum[i]<<endl;
            if (p!=-1) ans=min(ans, i-p);
        }
        return ans==n+1?-1:ans;
    }

X. https://blog.csdn.net/yanglingwell/article/details/80875790
朴素思想(O(n)^2, TLE)
记 ，前 x 数（包括第 x 个数）的和为 frontSum[x]， 则第 i 个数到第 j 个数的和为 frontSum[j]-frontSum[i-1]。
遍历 i, j 的情况，求出和大于等于 K， 且长度最小的数组即可。复杂度 O(n^2)。

  int shortestSubarray(vector<int>& A, int K) {

    // 前序和

    vector<long long int> frontSum(A.size()+1, 0);

    for(int i = 1; i <= A.size(); ++i)

    {

        frontSum[i] = frontSum[i-1] + A[i-1];

    }

    int ans = -1;

    // 枚举所有情况

    for(int i = 0; i < A.size(); ++i)

    {

        for(int j = i; j < A.size(); ++j)

        {

            if(frontSum[j+1] - frontSum[i] >= K && (ans == -1 || ans > j+1-i))

            {

                ans = j+1-i;

                break;

            }

        }

    }

    return ans;

 }

https://www.geeksforgeeks.org/minimum-length-subarray-sum-greater-given-value/

Given an array of positive integers and a number x, find the smallest subarray with sum greater than the given value.

    // Returns length of smallest subarray with sum greater than x.

    // If there is no subarray with given sum, then returns n+1

    static int smallestSubWithSum(int arr[], int n, int x) 

    {

        // Initialize current sum and minimum length

        int curr_sum = 0, min_len = n + 1;

  

        // Initialize starting and ending indexes

        int start = 0, end = 0;

        while (end < n) 

        {

            // Keep adding array elements while current sum

            // is smaller than x

            while (curr_sum <= x && end < n)

                curr_sum += arr[end++];

  

            // If current sum becomes greater than x.

            while (curr_sum > x && start < n) 

            {

                // Update minimum length if needed

                if (end - start < min_len)

                    min_len = end - start;

  

                // remove starting elements

                curr_sum -= arr[start++];

            }

        }

        return min_len;

    }




The above solution may not work if input array contains negative numbers. For example arr[] = {- 8, 1, 4, 2, -6}. To handle negative numbers, add a condition to ignore subarrays with negative sums.

static int smallestSubWithSum(int arr[], 

                              int n, int x)

{

    // Initialize current 

    // sum and minimum length

    int curr_sum = 0, min_len = n + 1;

  

    // Initialize starting

    // and ending indexes

    int start = 0, end = 0;

    while (end < n)

    {

        // Keep adding array 

        // elements while current 

        // sum is smaller than x

        while (curr_sum <= x && end < n)

        {

            // Ignore subarrays with 

            // negative sum if x is

            // positive.

            if (curr_sum <= 0 && x > 0)

            {

                start = end;

                curr_sum = 0;

            }

  

            curr_sum += arr[end++];

        }

  

        // If current sum becomes 

        // greater than x.

        while (curr_sum > x && start < n)

        {

            // Update minimum

            // length if needed

            if (end - start < min_len)

                min_len = end - start;

  

            // remove starting elements

            curr_sum -= arr[start++];

        }

    }

    return min_len;

}