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];
int ans = N+1; // n+1 is impossible
Deque<Integer> monoq = new LinkedList();
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()] <= 0) {
monoq.removeLast();
}
while (!monoq.isEmpty() && P[y] - P[monoq.getFirst()] >= K) {
ans = Math.min(ans, y - monoq.removeFirst());
}
// 0 < sum region < k
monoq.addLast(y);
}
return ans < N+1 ? ans : -1;
}
}