图解 LeetCode 难题：「和至少为 K 的最短子数组」

浅浅的花香味﹌ 2024-04-18 19:23 30阅读 0赞

点击蓝色“五分钟学算法”关注我哟

加个“星标”，天天中午 12:15，一起学算法

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg]

作者 | P.yh

来源 | 五分钟学算法

今天分享的题目来源于 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` 这个位置踢出队列即可。

另外就是我们如何计算答案呢？那就是我们从队列中最小的位置开始计算，如果符合条件，我们就记录答案，并将这个位置踢出队列，道理很简单，再往后遍历不可能会有比这个还要小的符合条件的长度。

### 图片描述 ###

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 1]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 2]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 3]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 4]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 5]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 6]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 7]

### 代码实现 ###

public int shortestSubarray(int[] A, int K) {
        ArrayDeque<Integer> 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 i = 0; i < sum.length; ++i) {
            if (i != 0) {
                while (dq.size() > 0 && sum[dq.peekLast()] >= sum[i]) {
                    dq.pollLast();
                }
    
                while (dq.size() > 0 && sum[i] - sum[dq.peekFirst()] >= K) {
                    minLength = Math.min(minLength, i - dq.pollFirst());
                }
            }
    
            dq.addLast(i);
        }
    
        return minLength == Integer.MAX_VALUE ? -1 : minLength;
    }

### 知识点 ###

前缀和、单调双端队列、数组

![640?][640]

**有热门推荐?**

1.【程序员】[全球最厉害的 14 位程序员][14]

2.【GitHub】[我在 GitHub 上看到了一个丧心病狂的开源项目！][GitHub]

3.【算法】[动画：七分钟理解什么是KMP算法][KMP]

4.【数据结构】[十大经典排序算法动画与解析，看我就够了][Link 1]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 8]

[640_wx_fmt_jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/24b7153b1d434be1b66767ff6eba27dc.png
[640_wx_fmt_jpeg 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/2f9ed13d9cdf4e0faa35f370bd8b5165.png
[640_wx_fmt_jpeg 2]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/6e35d7ae93f941ed80fdf4ff1d3ac676.png
[640_wx_fmt_jpeg 3]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/944a893d1cd04e59a62c3ef37e245d50.png
[640_wx_fmt_jpeg 4]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/41935571a6754d9f9f8c63e1bbbd18e0.png
[640_wx_fmt_jpeg 5]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/2c65b724c2c74c4a8fc4ea99c1dfa795.png
[640_wx_fmt_jpeg 6]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/72d2382ae7204799a880d21b2f48a269.png
[640_wx_fmt_jpeg 7]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/7088b2dd6b7c45a380c7357e201ff98c.png
[640]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/ef918a315ac745e4bd3d3e46c2d47d54.gif
[14]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247486099&idx=1&sn=6ea84944fe6a3d6dd1af2b00f3e53002&chksm=fa0e6512cd79ec04c8e8c63e74d78cc23629b88290a8e0642e5e44601f99fc39a3ea530867bc&scene=21#wechat_redirect
[GitHub]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247486254&idx=1&sn=654c208601879fe1b76c682a069a4e6a&chksm=fa0e64afcd79edb960a9863c7af7e6de5893da2326e6eca2bcd9d68061966d200ba0e189ab91&scene=21#wechat_redirect
[KMP]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247485939&idx=1&sn=b25f39b5644da92c4047bbbd9936f73c&chksm=fa0e6672cd79ef64dda0a21e23c2817edf4a64cbb75b9bed328d6519c6cd4fef36d03a4cb309&scene=21#wechat_redirect
[Link 1]: https://blog.csdn.net/dQCFKyQDXYm3F8rB0/article/details/87910210
[640_wx_fmt_jpeg 8]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/d94040d444fc4b99985081b13a0fa341.png