README.md

862. 和至少为 K 的最短子数组

English Version

题目描述

给你一个整数数组 nums 和一个整数 k ，找出 nums 中和至少为 k 的 最短非空子数组 ，并返回该子数组的长度。如果不存在这样的 子数组 ，返回 -1 。

子数组 是数组中 连续 的一部分。

 

示例 1：

输入：nums = [1], k = 1
输出：1

示例 2：

输入：nums = [1,2], k = 4
输出：-1

示例 3：

输入：nums = [2,-1,2], k = 3
输出：3

 

提示：

• 1 <= nums.length <= 105
• -105 <= nums[i] <= 105
• 1 <= k <= 109

解法

方法一：单调队列

Python3

class Solution:
    def shortestSubarray(self, nums: List[int], k: int) -> int:
        s = [0] + list(accumulate(nums))
        ans = inf
        q = deque([0])
        for i in range(1, len(s)):
            while q and s[i] - s[q[0]] >= k:
                ans = min(ans, i - q.popleft())
            while q and s[i] <= s[q[-1]]:
                q.pop()
            q.append(i)
        return -1 if ans == inf else ans

Java

class Solution {
    public int shortestSubarray(int[] nums, int k) {
        int n = nums.length;
        long[] s = new long[n + 1];
        for (int i = 0; i < n; ++i) {
            s[i + 1] = s[i] + nums[i];
        }
        Deque<Integer> q = new ArrayDeque<>();
        q.offer(0);
        int ans = Integer.MAX_VALUE;
        for (int i = 1; i <= n; ++i) {
            while (!q.isEmpty() && s[i] - s[q.peek()] >= k) {
                ans = Math.min(ans, i - q.poll());
            }
            while (!q.isEmpty() && s[i] <= s[q.peekLast()]) {
                q.pollLast();
            }
            q.offer(i);
        }
        return ans == Integer.MAX_VALUE ? -1 : ans;
    }
}

C++

class Solution {
public:
    int shortestSubarray(vector<int>& nums, int k) {
        int n = nums.size();
        vector<long long> s(n + 1);
        for (int i = 0; i < n; ++i) s[i + 1] = s[i] + nums[i];
        deque<int> q {{0}};
        int ans = INT_MAX;
        for (int i = 1; i <= n; ++i) {
            while (!q.empty() && s[i] - s[q.front()] >= k) {
                ans = min(ans, i - q.front());
                q.pop_front();
            }
            while (!q.empty() && s[i] <= s[q.back()]) q.pop_back();
            q.push_back(i);
        }
        return ans == INT_MAX ? -1 : ans;
    }
};

Go

func shortestSubarray(nums []int, k int) int {
	n := len(nums)
	s := make([]int, n+1)
	for i, v := range nums {
		s[i+1] = s[i] + v
	}
	q := []int{0}
	ans := math.MaxInt32
	for i := 1; i <= n; i++ {
		for len(q) > 0 && s[i]-s[q[0]] >= k {
			ans = min(ans, i-q[0])
			q = q[1:]
		}
		for len(q) > 0 && s[i] <= s[q[len(q)-1]] {
			q = q[:len(q)-1]
		}
		q = append(q, i)
	}
	if ans == math.MaxInt32 {
		return -1
	}
	return ans
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

...