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

Link

力扣

Problem

给你一个整数数组 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

Solution

Go

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

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

C++