今天分享的题目来源于 LeetCode 上第 862 号问题：和至少为 K 的最短子数组。题目难度为 Hard 。
题目描述
返回
A
的最短的非空连续子数组的长度，该子数组的和至少为
K
。
如果没有和至少为
K
的非空子数组，返回
-1
。
示例 1：
输入：A = [1], K = 1
输出：1
示例 2：
输入：A = [1,2], K = 4
输出：-1
示例 3：
输入：A = [2,-1,2], K = 3
输出：3
提示：
1 <= A.length <= 50000
-10 ^ 5 <= A[i] <= 10 ^ 5
1 <= K <= 10 ^ 9
题目解析
在给定的一个数组中，找出一个最短的子数组，子数组中所有元素的和必须不小于 K。
刚拿到这道题的时候感觉貌似很简单，用两个指针同向而行，这两个指针之间确定了一个子数组，先移动右指针，每当满足条件，我们就试着移动左指针，到条件不满足就停止，就好像一个
滑动窗口
一样，但是这个做法其实是错误的！
比如测试样例为
[1,-100,1,2] 3
，如果按上述方法来做，会找不到答案。
改进一下？
在这基础之上改变后，用两个嵌套循环，当我们右指针每移动到一个点，不管是否满足条件，左指针就从 0 开始移动缩小数组的距离，一直将数组的大小缩减为 0，再继续循环。
这个思路是 work 的，但是对于这道题来说时间过高，报了 TLE。
一开始还真不知道怎样优化，这次总结经验，感觉
以后实在想不出来的题可以先尝试换换数据结构，就是一开始试着确定数据结构，而不是算法，因为数据结构是算法成功运作的前提
。
对于这道题来说，如果不借助数据结构，我能想到的就只有前面提到的暴力解法。如果仔细看这道题，其实是求数组的区间的值，如果我们能够快速获得区间的值就更好了，常规的暴力求解就是将所求解的区间遍历一遍，这种方法在频繁请求获取区间值的需求下会存在大量的重复计算，有一个巧妙的方法是保存数组的
前缀和数组
，就是
sum[i] = array[0] + array[1] + array[2] + ... + array[i - 1]
，有了这个数组，我们就可以很方便地求解任意区间的和。
比如说我们要求区间 [3, 5] 的和, 那么就可以用
sum[6] - sum[3]
，注意这里的前缀和数组为了计算方便，增加了一位，
sum[0] = 0
，前缀和数组的长度是原数组的长度加 1。
有了这个数组，你可能对这道题还是一头雾水，别急，这时就是我们前面提到的数据结构登场的时候，我们每遍历到数组当中的一个位置，往回看怎样才能清楚前面哪个区间是符合条件的呢？把前面的位置再重新遍历一遍？那这就又回到了我们前面的暴力方法，肯定不是。
换句话说我们要根据条件考虑前面的位置，这个考虑是在遍历的时候就考虑，而不用我们从头再去重复劳动，一开始我想到了队列，但是这个其实不准确，严格来说是
单调双端队列
，也就是说这个队列头尾都可以出，而且里面存的元素是单调递增或者递减的，这有个什么好处呢？
假如说我们当前考虑位置 i，这时区间
[0, i]
的值比区间
[0, i - 1]
的还要小，那么对于后面的位置，我们其实就不需要考虑了 i - 1 了，因为位置
sum[n] - sum[i] > sum[n] - sum[i - 1]
，而且就长度来说的话
[i, n]
比
[i - 1, n]
更短，因此我们可以把 i - 1 这个位置踢出队列。
换句话说，也就是如果数组里面都是正数，那么长度越长，区间和肯定越大，则 sums[i] 一定大于所有双向队列中的区间和，但由于可能存在负数，从而使得长度变长，区间总和反而减少了，所以如果出现上面这种情况直接将
i - 1
这个位置踢出队列即可。
另外就是我们如何计算答案呢？那就是我们从队列中最小的位置开始计算，如果符合条件，我们就记录答案，并将这个位置踢出队列，道理很简单，再往后遍历不可能会有比这个还要小的符合条件的长度。
图片描述
代码实现
public int shortestSubarray(int[] A, int K) {
ArrayDeque dq = new ArrayDeque<>();
int minLength = Integer.MAX_VALUE;
int[] sum = new int[A.length + 1];
for (int i = 1; i <= A.length; ++i) {
sum[i] = sum[i - 1] + A[i - 1];
}
for (int
