862. Shortest Subarray with Sum at Least K

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`

862. Shortest Subarray with Sum at Least K
``````struct Solution;

use std::collections::VecDeque;

impl Solution {
fn shortest_subarray(a: Vec<i32>, k: i32) -> i32 {
let n = a.len();
let mut queue: VecDeque<usize> = VecDeque::new();
let mut prefix = vec![0; n + 1];
queue.push_back(0);
let mut res = std::usize::MAX;
for i in 0..n {
prefix[i + 1] = prefix[i] + a[i];
while let Some(&j) = queue.front() {
if prefix[i + 1] - prefix[j] >= k {
res = res.min(i + 1 - j);
queue.pop_front();
} else {
break;
}
}
while let Some(&j) = queue.back() {
if prefix[i + 1] <= prefix[j] {
queue.pop_back();
} else {
break;
}
}
queue.push_back(i + 1);
}
if res == std::usize::MAX {
-1
} else {
res as i32
}
}
}

#[test]
fn test() {
let a = vec![1];
let k = 1;
let res = 1;
assert_eq!(Solution::shortest_subarray(a, k), res);
let a = vec![1, 2];
let k = 4;
let res = -1;
assert_eq!(Solution::shortest_subarray(a, k), res);
let a = vec![2, -1, 2];
let k = 3;
let res = 3;
assert_eq!(Solution::shortest_subarray(a, k), res);
}
``````