题目:
返回 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.创建一个数组,其中P[i] = A[0]+A[1]+ ...+ A[i](如果A[i]没有负数可以保证P[i+1]>P[i])则本题转换为P[y]-P[x]>=k且y-x最小的值
2.使用双端队列保存滑动窗口值(js可以直接使用数组),每次循环在队列尾添加本次循环的下标j,记为滑动窗口末尾值,为了保证P[j+1]>P[j],因此while(queue.length!=0 && P[queue[queue.length-1]] >=P[j]){queue.pop()},当queue.length!=0 && P[j]-P[queue[0]]>=K时判断最新的滑动窗口初始值
作者:witch
链接:https://leetcode-cn.com/problems/shortest-subarray-with-sum-at-least-k/solution/jsban-ben-de-hua-dong-chuang-kou-by-witch/
来源:力扣(LeetCode)
时间复杂度O(n)
空间复杂度O(n)
var shortestSubarray = function(A, K) {
let len = A.length;
let min = len + 1;
let quene = [];
let P = new Array(len).fill(0);
for(let i = 0; i < len; i++){
P[i + 1] = A[i] + P[i];
}
for(let j = 0; j <= len; j++){
while(quene.length && P[quene[quene.length - 1]] > P[j]){
quene.pop()
}
while(quene.length && P[j] - P[quene[0]] >= K){
min = Math.min(min, j - quene[0])
quene.shift();
}
quene.push(j);
}
return min < len + 1 ? min : -1;
};