Comment on page

# 862.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 <= A.length <= 50000
-10 ^ 5 <= A[i] <= 10 ^ 5
1 <= K <= 10 ^ 9

## 代码

### Approach #1 Sliding Window

Time: O(N) && Space: O(N)
class Solution {
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]; // prefix sum
}
int ans = N + 1;
for (int y = 0; y < P.length; y++) {
while (!monoq.isEmpty() && P[y] <= P[monoq.getLast()]) {
monoq.removeLast(); // decreasing sequence
}
while (!monoq.isEmpty() && P[y] >= P[monoq.getFirst()] + K) {
ans = Math.min(ans, y - monoq.removeFirst());
}
}
return ans < N + 1 ? ans : -1;
}
}

### #2

public int shortestSubarray(int[] A, int K) {
int N = A.length;
int 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();