862 Shortest Subarray with Sum at Least K

862. Shortest Subarray with Sum at Least K

1. Question

Return the length of the shortest, non-empty, contiguous subarray ofAwith sum at leastK.

If there is no non-empty subarray with sum at leastK, 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

2. Implementation

(1) Deque

思路:

• 要得到subarray sum，我们需要先构建prefixSum数组，通过prefixSum数组，我们可以迅速的得到subarray[i, j]的和是prefixSum[j - 1] - prefixSum[i]

• 由于题目要我们找到最短的subarray，且subarray和大于等于K，所以我们可以通过一个双向队列deque，当deque不为空且prefixSum[i] - prefixSum[deque.getFirst()] 大于等于K时，我们得到一个解，更新res

• 同时我们需要注意数组会存在负数或者0的情况，在这种情况下，如果prefixSum[i] <= prefixSum[dequeu.getLast()]，由于i > deque.getLast()， prefixSum[i]比prefixSum[deque.getLast()]小，说明从i开始的区间不仅比deque.getLast()开始的区间更有机会比K大，同时最后得到的区间也会更小，所以我们可以删除deque.getLast()上的位置，而保留i

class Solution {
    public int shortestSubarray(int[] A, int K) {
        int n = A.length;

        int[] prefixSum = new int[n + 1];

        for (int i = 0; i < n; i++) {
            prefixSum[i + 1] = prefixSum[i] + A[i];
        }

        Deque<Integer> deque = new ArrayDeque();
        int res = n + 1;

        for (int i = 0; i <= n; i++) {
            // 找到符合条件subarray, 更新res
            while (deque.size() > 0 && prefixSum[i] - prefixSum[deque.getFirst()] >= K) {
                res = Math.min(res, i - deque.removeFirst());
            }

            // i > deque.getLast(), 如果prefixSum[i] <= prefixSum[deque.getLast()], 说明[deque.getLast(), i]之间出现0或负数
            // 说明prefixSum[i]能让最后的subarray sum更大，同时使得符合条件的subarray长度更短，所以我们可以删除dequeu.getLast()
            while (deque.size() > 0 && prefixSum[i] <= prefixSum[deque.getLast()]) {
                deque.removeLast();
            }

            deque.addLast(i);
        }
        return res <= n ? res : -1;
    }
}

3. Time & Space Complexity

Deque: 时间复杂度O(n), 空间复杂度O(n)