【2022-10-26每日一题】862. 和至少为 K 的最短子数组[Hard]

2022-10-26每日一题：862. 和至少为 K 的最短子数组

难度：Hard

标签：队列 、 数组 、 二分查找 、 前缀和 、 滑动窗口 、 单调队列 、 堆（优先队列）

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

方法一：前缀和 + 单调双端队列

• 推荐题解

func shortestSubarray(nums []int, k int) int {
    n := len(nums)
    preSum := make([]int, n+1)
    for i, num := range nums {
        preSum[i+1] = preSum[i] + num // 计算前缀和
    }
    
    ans := n + 1
    q := []int{}
    for i, curSum := range preSum {
        for len(q) > 0 && curSum - preSum[q[0]] >= k {
            ans = min(ans, i-q[0])
            q = q[1:]  // 上面计算后 q[0] 没有用了，直接移除
        }
        for len(q) >0 && preSum[q[len(q)-1]] >= curSum {
            q = q[:len(q)-1] // 移除队列中大约等于当前数的元素
        }
        q = append(q, i)
    }
    if ans < n + 1 {
        return ans
    }
    return -1
}

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

复杂度分析

LeetCode题库地址

• https://leetcode.cn/problems/shortest-subarray-with-sum-at-least-k