首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >图解 LeetCode 难题:「和至少为 K 的最短子数组」

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

作者头像
五分钟学算法
发布2019-09-12 12:49:30
3.1K0
发布2019-09-12 12:49:30
举报
文章被收录于专栏:五分钟学算法五分钟学算法

作者 | 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 这个位置踢出队列即可。

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

图片描述

代码实现

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;
}
本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2019-09-10,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 五分钟学算法 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 题目描述
  • 题目解析
  • 图片描述
  • 代码实现
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档