862. Shortest Subarray with Sum at Least K
Return the length of the shortest, non-empty, contiguous subarray of nums with sum at least k.
If there is no non-empty subarray with sum at least k, return -1.
Example 1:
Input: nums = [1], k = 1
Output: 1
Example 2:
Input: nums = [1,2], k = 4
Output: -1
Example 3:
Input: nums = [2,-1,2], k = 3
Output: 3
Note:
- 1 <= nums.length <= 50000
- -105 <= nums[i] <= 105
- 1 <= k <= 109
public int shortestSubarray(int[] A, int K) {
int N = A.length, res = N + 1;
int[] B = new int[N + 1];
for (int i = 0; i < N; i++) B[i + 1] = B[i] + A[i];
Deque<Integer> d = new ArrayDeque<>();
for (int i = 0; i < N + 1; i++) {
while (d.size() > 0 && B[i] - B[d.getFirst()] >= K)
res = Math.min(res, i - d.pollFirst());
while (d.size() > 0 && B[i] <= B[d.getLast()])
d.pollLast();
d.addLast(i);
}
return res <= N ? res : -1;
}