CloudLander's Blog
0%

未排序数组中累加和小于或等于给定值的最长子数组长度

发表于 分类于

未排序数组中累加和小于或等于给定值的最长子数组长度

给定一个无序数组arr，其中元素可正可负可0，给定一个整数k，求arr所有子数组中累加和小于或等于k的最长子数组长度。
例如：arr=[3,-2,-4,0,6], k=-2，相加和小于或等于-2的最长子数组为3,-2,-4,0 所以结果返回4
依次求以数组的每个位置结尾的，累加和小于或等于k的最长子数组长度，其中最长的那个子数组长度就是我们要的结果。

假如处理到位置30，从位置0到位置30的累加和是100（sum[0..30]=100）,现在想求以位置30结尾的、累加和小于或等于10的最长子数组长度。再假设从位置0开始累加到位置10的时候，累加和第一次大于或等于90(sum[0..10]>=90)，那么可以知道以位置30结尾的相加和小于或等于10的最长子数组就是arr[11..30]。也就是说，如果从0位置到j位置的累加和为sum[0..j]，此时想求以j位置结尾的相加和小于或等于k的最长子数组长度。那么只要知道大于或等于sum[0..j]-k这个值的累加和最早出现在j之前的什么位置就可以，假设那个位置是i位置，那么arr[i+1..j]就是j位置结尾的相加和小于或等于k的最长数组。

由于不是具体值，而是范围值，所以不能直接用hashmap，为了方便地找到大于或等于某一个值的累加和最早出现的位置，可以按照如下方法生成辅助数组helpArr。
1.首先生成arr每个位置从左到右的累加和数组sumArr。以[1,2,-1,5,-2]为例，生成的sumArr=[0,1,3,2,7,5]。注意，sumArr中第一个数为0，表示当没有任何一个数时的累加和为0.
2.生成sumArr的左侧最大值数组helpArr，sumArr={0,1,3,2,7,5} -> {0,1,3,3,7,7}。因为我们只关心大于或等于某个值的累加和最早出现的位置，而累加和3出现在2之前，并且大于或等于3必然大于2，所以当前要保留一个更大的、出现更早的累加和。
3.helpArr是sumArr每个位置上的左侧最大值数组，那么它当然是有序的，在这样一个有序的数组中，就可以二分查找大于或等于某一个值的累加和最早出现的位置。例如，在[0,1,3,3,7,7]中查找大于或等于4这个值的位置，就是第一个7的位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
public int maxLength(){
    int[] h = new int[arr.length+1];
    int sum = 0;
    h[0] = sum;
    for(int i=0;i!=arr.length;i++){
        sum += arr[i];
        h[i+1] = Math.max(sum, h[i]);
    }
    sum = 0;
    int res = 0;
    int pre = 0;
    int len = 0;
    for(int i=0;i!=arr.length;i++){
        sum+=arr[i];
        pre = getLessIndex(h, sum-k);
        len = pre == -1?0:i-pre+1;
        res = Math.max(res, len);
    }
    return res;
}


public int getLessIndex(int[] arr, int num){
    int low = 0;
    int high = arr.length-1;
    int mid = 0;
    int res = -1;
    while(low<=high){
        mid = (low+high)>>1;
        if(arr[mid]>=num){
            res = mid;
            high = mid -1;
        }else{
            low = mid+1;
        }
    }
    return res;
}