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

### Link

{% embed url="<https://leetcode.cn/problems/shortest-subarray-with-sum-at-least-k/>" %}

### Problem

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

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

示例 1：

{% code overflow="wrap" %}

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

{% endcode %}

示例2：

{% code overflow="wrap" %}

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

{% endcode %}

示例3:

{% code overflow="wrap" %}

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

{% endcode %}

提示：

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

### Solution

{% tabs %}
{% tab title="Go" %}

```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
}
```

{% endtab %}

{% tab title="C++" %}

<pre class="language-cpp"><code class="lang-cpp"><strong>
</strong></code></pre>

{% endtab %}
{% endtabs %}