返回 A 的最短的非空连续子数组的长度，该子数组的和至少为 K 。
如果没有和至少为 K 的非空子数组，返回 -1。
示例 1：
输入：A = [1], K = 1
输出：1
示例 2：
输入：A = [1,2], K = 4
输出：-1
示例 3：
输入：A = [2,-1,2], K = 3
输出：3
提示：
1 <= A.length <= 50000
-10 ^ 5 <= A[i] <= 10 ^ 5
1 <= K <= 10 ^ 9
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shortest-subarray-with-sum-at-least-k
一开始写法写成了最大连续子数组，写错了
class Solution {
public int shortestSubarray(int[] A, int K) {
//最大连续子序列
int ans = -1,sum = 0,last = 0;
for(int i=0;i<A.length;i++){
sum+=A[i];
if(sum>=K){
if(ans==-1) ans = i - last + 1;
else ans = Math.min( ans , i - last + 1);
}
if(sum<=0){
sum = 0;
last = i;
}
}
return ans;
}
}
这是网友提供的答案
https://cloud.tencent.com/developer/article/1505345
class Solution{
public int shortestSubarray(int[] A, int K) {
ArrayDeque<Integer> dq = new ArrayDeque<>();
int minLength = Integer.MAX_VALUE;
int[] sum = new int[A.length + 1];
//前缀和数组
for(int i = 1; i <= A.length; ++i){
sum[i] = sum[i - 1] + A[i - 1];
}
for(int i = 0; i< sum.length;++i){
if(i != 0 ){
while(dq.size() > 0 && sum[dq.peekLast()] >= sum[i]){
dq.pollLast();
}
while(dq.size() > 0 && sum[i] - sum[dq.peekFirst()] > K){
minLength = Math.min(minLength, i - dq.pollFirst());
}
}
dq.addLast(i);
}
return minLength == Integer.MAX_VALUE ? -1 : minLength;
}
}
