LeetCode 862. Shortest Subarray with Sum at Least K

ID	Title	Difficulty
Loading...

JIAKAOBO

LeetCode

感谢赞助!

㊗️
大家
offer
多多！

Problem

Given an integer array nums and an integer k, return the length of the shortest non-empty subarray of nums with a sum of at least k. If there is no such subarray, return -1.

A subarray is a contiguous part of an array.

Example 1:

Input: nums = [1], k = 1
Output: 1

Example 2:

Input: nums = [1,2], k = 4
Output: -1

Example 3:

Input: nums = [2,-1,2], k = 3
Output: 3

Constraints:

$1 <= nums.length <= 10^5$
$-10^5 <= nums[i] <= 10^5$
$1 <= k <= 10^9$

Code

209. Minimum Size Subarray Sum

class Solution {
    public int shortestSubarray(int[] nums, int k) {
        int res = nums.length + 1;
        long[] sums = new long[nums.length + 1];

        for (int i = 0; i < nums.length; i++) {
            sums[i + 1] = sums[i] + nums[i];
        }

        Deque<Integer> queue = new LinkedList<>();

        for (int i = 0; i <= nums.length; i++) {
            while (queue.size() > 0 && sums[i] - sums[queue.getFirst()] >= k) {
                res = Math.min(res, i - queue.pollFirst());
            }

            while (queue.size() > 0 && sums[i] <= sums[queue.getLast()]) {
                queue.pollLast();
            }

            queue.addLast(i);
        }

        return res <= nums.length ? res : -1;
    }
}