# 862     Shortest Subarray with Sum at Least K

## 862. [Shortest Subarray with Sum at Least K](https://leetcode.com/problems/shortest-subarray-with-sum-at-least-k/description/)

## 1. Question

Return the **length** of the shortest, non-empty, contiguous subarray of`A`with sum at least`K`.

If there is no non-empty subarray with sum at least`K`, return`-1`.

**Example 1:**

```
Input: A = [1], K = 1
Output: 1
```

**Example 2:**

```
Input: A = [1,2], K = 4
Output: -1
```

**Example 3:**

```
Input: A = [2,-1,2], K = 3
Output: 3
```

**Note:**

1. `1 <= A.length <= 50000`
2. `-10 ^ 5 <= A[i] <= 10 ^ 5`
3. `1 <= K <= 10 ^ 9`

## 2. Implementation

**(1) Deque**

思路:

* 要得到subarray sum，我们需要先构建prefixSum数组，通过prefixSum数组，我们可以迅速的得到subarray\[i, j]的和是prefixSum\[j - 1] - prefixSum\[i]
* 由于题目要我们找到最短的subarray，且subarray和大于等于K，所以我们可以通过一个双向队列deque，当deque不为空且prefixSum\[i] - prefixSum\[deque.getFirst()] 大于等于K时，我们得到一个解，更新res
* 同时我们需要注意数组会存在负数或者0的情况，在这种情况下，如果prefixSum\[i] <= prefixSum\[dequeu.getLast()]，由于i > deque.getLast()， prefixSum\[i]比prefixSum\[deque.getLast()]小，说明从i开始的区间不仅比deque.getLast()开始的区间更有机会比K大，同时最后得到的区间也会更小，所以我们可以删除deque.getLast()上的位置，而保留i

```java
class Solution {
    public int shortestSubarray(int[] A, int K) {
        int n = A.length;

        int[] prefixSum = new int[n + 1];

        for (int i = 0; i < n; i++) {
            prefixSum[i + 1] = prefixSum[i] + A[i];
        }

        Deque<Integer> deque = new ArrayDeque();
        int res = n + 1;

        for (int i = 0; i <= n; i++) {
            // 找到符合条件subarray, 更新res
            while (deque.size() > 0 && prefixSum[i] - prefixSum[deque.getFirst()] >= K) {
                res = Math.min(res, i - deque.removeFirst());
            }

            // i > deque.getLast(), 如果prefixSum[i] <= prefixSum[deque.getLast()], 说明[deque.getLast(), i]之间出现0或负数
            // 说明prefixSum[i]能让最后的subarray sum更大，同时使得符合条件的subarray长度更短，所以我们可以删除dequeu.getLast()
            while (deque.size() > 0 && prefixSum[i] <= prefixSum[deque.getLast()]) {
                deque.removeLast();
            }

            deque.addLast(i);
        }
        return res <= n ? res : -1;
    }
}
```

## 3. Time & Space Complexity

**Deque**: 时间复杂度O(n), 空间复杂度O(n)
