862. 和至少为 K 的最短子数组-前缀和/数组/滑动窗口-困难

问题描述

返回 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;
    }
}
*/

 

上一篇:洛谷P1880 [NOI1995]石子合并 #区间DP#


下一篇:LeetCode 862. 和至少为 K 的最短子数组(前缀和+deque单调栈)