前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >2022-04-17:给定一个数组arr,其中的值有可能正、负、0,给定一个正数k。

2022-04-17:给定一个数组arr,其中的值有可能正、负、0,给定一个正数k。

作者头像
福大大架构师每日一题
发布2022-06-04 10:33:02
3570
发布2022-06-04 10:33:02
举报

2022-04-17:给定一个数组arr,其中的值有可能正、负、0,

给定一个正数k。

返回累加和>=k的所有子数组中,最短的子数组长度。

来自字节跳动。力扣862。

答案2022-04-17:

看到子数组,联想到结尾怎么样,开头怎么样。

预处理前缀和,单调栈。

达标的前缀和,哪一个离k最近?

单调栈+二分。复杂度是O(N*logN)。

双端队列。

时间复杂度:O(N)。

代码用rust编写。代码如下:

代码语言:javascript
复制
fn main() {
    let arr: Vec<isize> = vec![2, -1, 2];
    let K: isize = 3;
    let ret = shortest_subarray2(arr, K);
    println!("{}", ret);
}

const MAXVALUE: isize = 9223372036854775807;

fn shortest_subarray2(arr: Vec<isize>, K: isize) -> isize {
    let N = arr.len();
    let mut sum: Vec<isize> = vec![];
    for i in 0..N + 1 {
        sum.push(0);
    }
    for i in 0..N {
        sum[i + 1] = sum[i] + arr[i];
    }
    let mut ans: isize = MAXVALUE;
    let mut dq: Vec<isize> = vec![];
    for i in 0..N + 1 {
        dq.push(0);
    }
    let mut l: isize = 0;
    let mut r: isize = 0;
    for i in 0..N + 1 {
        // 头部开始,符合条件的,从头部弹出!
        while l != r && sum[i] - sum[dq[l as usize] as usize] >= K {
            ans = get_min(ans, i as isize - dq[l as usize]);
            l += 1;
        }
        // 尾部开始,前缀和比当前的前缀和大于等于的,从尾部弹出!
        while l != r && sum[dq[(r - 1) as usize] as usize] >= sum[i as usize] {
            r -= 1;
        }
        dq[r as usize] = i as isize;
        r += 1;
    }
    if ans != MAXVALUE {
        ans
    } else {
        -1
    }
}

fn get_min(a: isize, b: isize) -> isize {
    if a < b {
        a
    } else {
        b
    }
}

执行结果如下:

***

[左神java代码](https://github.com/algorithmzuo/blob/main/src/class_2022_01_3_week/Code03_ShortestSubarrayWithSumAtLeastK.java)

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2022-04-17,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 福大大架构师每日一题 微信公众号,前往查看

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

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

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档