专栏首页mathor子数组累加和为aim(小于等于aim)的三个问题

子数组累加和为aim(小于等于aim)的三个问题

子数组累加和为aim(小于等于aim)的三个问题

  • 累加和等于aim的最长子数组的长度(数组可正可负可零)
  • 累加和等于aim的最长子数组的长度(数组只有正数)
  • 累加和小于等于aim的最长子数组的长度(数组可正可负可零)

累加和等于aim的最长子数组的长度(数组可+,-,0)

 这道题我另有文章讲解了,这里就不多说了

累加和等于aim的最长子数组的长度(数组只有正数)

 这个和上面唯一的不同就是数组中只有正数,这里使用类似窗口移动的做法,给出两个指针,L,R表示窗口的左右边界 ,sum表示的是arr[L,R]之间的累加和,L,R一直往右动。

  • 如果窗口内sum < aim,R就往右扩,并且sum += arr[R];
  • 如果窗口内sum > aim,L 就往右扩,并且sum -= arr[L];
  • 如果窗口内sum = aim, 就说明这个窗口内累加和为sum ,此时记录最大值即可;
public static int getMax(int[] arr,int aim){
    if(arr == null || arr.length == 0 || aim < 0)return 0;
    int L = 0,R = 0;
    int res = 0, sum = arr[0];
    while(R < arr.length){
        if(sum == aim){
            res = Math.max(res,R - L + 1);
            sum -= arr[L++];
        }else if(sum < aim){//小于等于就往右边扩
            if(++R == arr.length) break;
            sum += arr[R];
        }else {           // 大于就往左边扩  sum > aim
            sum -= arr[L++];
        }
    }
    return res;
}

累加和小于等于aim的最长子数组的长度(数组可+,-,0)

 两个数组sum和ends,sum[i]表示的是以arr[i]开头(必须包含arr[i])的所有子数组的最小累加和,对应的ends[i]表示的是取得这个最小累加和的右边界。 一开始先求出sums数组和ends[]数组。

 这个题目最精华的是左右边界不回退,就是说,如果从0位置扩到T区间,T+1区间不能扩了,此时不是回到1位置开始扩,而是舍弃0位置,看能不能由于舍弃0位置把T+1位置加进来:

public static int getMaxLength2(int[] arr,int aim){
    if(arr == null || arr.length == 0)return 0;
    int[] sums = new int[arr.length]; //以arr[i]开头所有子数组的最小累加和
    int[] ends = new int[arr.length]; //取得最小累加和的最右边界
    sums[arr.length-1] = arr[arr.length-1];
    ends[arr.length-1] = arr.length-1;
    for(int i = arr.length - 2; i >= 0; i--){ //求出sums数组和ends数组
        if(sums[i+1] < 0){
            sums[i] = arr[i] + sums[i+1];
            ends[i] = ends[i+1];
        }else {
            sums[i] = arr[i];
            ends[i] = i;
        }
    }
    int sum = 0; //目前的累加和  sum -> R
    int R = 0;//每一次扩到的右边界
    int res = 0; //答案
    for(int start = 0; start < arr.length; start++){//每一次开头
        while(R < arr.length && sum + sums[R] <= aim){//一整块一整块的扩
            sum += sums[R];
            R = ends[R] + 1;
        }
        sum -= R > start ? arr[start] : 0;//如果R>start,下面start要++了,窗口内减去arr[start]
        res = Math.max(res,R - start);//窗口是start ~ R-1  ,所以是长度为R-start
        R = Math.max(R,start + 1);  //有没有可能扩不出去
    }
    return res;
  }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode325.最大子数组之和为k

     这道题暴力很好做,但是找技巧确实不好想,首先假设这么一个场景,从下标为0到下标为100,和sum = 2000,假设我们要求的目标k=800,那么我们只要...

    mathor
  • Dancing Links算法

     Dancing Links算法主要用于解决精确覆盖问题,精确覆盖问题就的定义:给定一个由0-1组成的矩阵,是否能找到一个行的集合,使得每个集合中每一列恰好只包...

    mathor
  • 第一章 计算机系统概述

     现代计算机都是冯诺依曼计算机,共由五大件组成:运算器、存储器、控制器,输入设备、输出设备

    mathor
  • LeetCode 545. 二叉树的边界(前序+后序)*

    给定一棵二叉树,以逆时针顺序从根开始返回其边界。 边界按顺序包括左边界、叶子结点和右边界而不包括重复的结点。 (结点的值可能重复)

    Michael阿明
  • 机器学习实践:用一个管道解决多个 Kaggle 竞赛问题(52PPT)

    【新智元导读】与机器学习不同,数据挖掘关注对特定问题及其数据的理解,针对每个问题设计最适合的解决方案。但本文作者却使用同一个管道,解决 3 个不同数据分析预测问...

    新智元
  • 亚马逊 Alexa Prize 比赛冠军团队专访:聊天机器人的突破与创新

    在 2017 年底结束的第一届亚马逊 Alexa Prize 比赛上,由华盛顿大学博士生方昊担任领队的 Sounding Board 团队在全球上百支队伍中突出...

    AI研习社
  • 双节棍「大师」鱼佬亲传武功秘籍:如何进行一场数据挖掘算法竞赛?

    简介:鱼遇雨欲语与余,Datawhale成员,武汉大学硕士,天池数据科学家。2019腾讯广告算法大赛冠军,数据竞赛爱好者。

    Datawhale
  • 浙大版《C语言程序设计(第3版)》题目集 练习7-7 矩阵运算

    给定一个n×n的方阵,本题要求计算该矩阵除副对角线、最后一列和最后一行以外的所有元素之和。副对角线为从矩阵的右上角至左下角的连线。

    C you again 的博客
  • 浙大版《C语言程序设计(第3版)》题目集 习题7-4 求矩阵各行元素之和

    输入第一行给出两个正整数m和n(1≤m,n≤6)。随后m行,每行给出n个整数,其间

    C you again 的博客
  • WPCOS插件实现WordPress图片/附件自动存储至腾讯云COS

    我们有些网站的图片和附件资源比较多,如果与网站文件存储在云服务器中,会同时占用服务器资源使得打开速度降低,这也是我们看到很多WordPress类的网站提到网站后...

    老蒋

扫码关注云+社区

领取腾讯云代金券