问题描述
返回 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
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/shortest-subarray-with-sum-at-least-k
解答
//前缀和+滑动窗口 class Solution { public int shortestSubarray(int[] A, int K) { int len = A.length; if(len == 0)return -1; long[] preSum = new long[len+1];//preSum[0] = 0 for(int i=1;i<=len;i++)preSum[i] = preSum[i-1]+A[i-1]; Deque<Integer> queue = new LinkedList<Integer>();//queue用来存放下标大并且值小的preSum元素的下标 int res = len+1;//len+1是不可能的长度 for(int i=0;i<=len;i++){//便利preSum while(!queue.isEmpty() && preSum[i]<=preSum[queue.getLast()]) queue.removeLast(); while(!queue.isEmpty() && preSum[i]-preSum[queue.getFirst()]>=K) res = Math.min(res, i-queue.removeFirst()); queue.addLast(i);//添加到队尾 } return res < len+1?res:-1; } } /*普通前缀和超时了,因为计算次数可以再减少。 class Solution { public int shortestSubarray(int[] A, int K) { int len = A.length; if(len == 0)return -1; long[] preSum = new long[len+1];//preSum[0] = 0 for(int i=1;i<=len;i++)preSum[i] = preSum[i-1]+A[i-1]; int start = 1; for(int step=1;start<=len;step++,start++){ for(int i=start;i<=len;i++){ if(preSum[i]-preSum[i-step]>=K)return step; } } return -1; } } */