子数组累加和为 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;
  }