CloudLander's Blog
0%

未排序数组中累加和为给定值的最长子数组系列问题

发表于 分类于

未排序数组中累加和为给定值的最长子数组系列问题

给定一个无序数组arr，其中元素可正可负可0，给定一个整数k，求arr所有子数组累加和为k的最长子数组长度

s(i)代表子数组arr[0..i]所有元素的累加和，那么子数组arr[j..i]（0<=j<=i< arr.length）的累加和为s(i)-s(j-1),解法：
1.设置变量sum=0,表示从0位置开始一直加到i位置所有元素的和，设置变量len=0，表示累加和为k的最长子数组长度，设置哈希表map，key表示从arr最左边开始累加过程中出现过的sum值，对应的value值则表示sum值最早出现的位置。
2.从左到右开始遍历，遍历的当前元素为arr[i].
1) 令sum=sum+arr[i],即之前所有元素的累加和s(i)，在map中查看是否存在sum-k.
》如果sum-k存在，从map中取出sum-k对应的value值，记为j，j代表从左到右不断累积啊的过程中第一次出现sum-k这个累加和的位置。根据之前的结论，arr[j+1..i]的累加和为s(i)-s(j)，此时s(i)=sum，又有s(j)=sum-k,所以arr[j+1..i]的累加和为k，同时因为map中只记录每一个累加和最早出现的位置，所以此时的arr[j+1..i]是必须以arr[i]结尾的所有子数组中，最长的累加和为k的子数组，如果该子数组的长度大于len，就更新len。
》如果sum-k不存在，说明在必须以arr[i]结尾的情况下没有累加和为k的子数组。
2）检查当前的sum(即s(i))是否在map中，如果不存在，说明此时的sum值是第一次出现
3.继续遍历下一个元素，直到所有元素都遍历完。

大体上过程如下，但还有很重要的问题，根据arr[j+1..i]的累加和为s(i)-s(j).如果从0位置开始累加，会导致j+1>=1，即所有从0位置开始的子数组都没考虑过，所有应该从-1这个位置开始累加，也就是遍历前先把(0,-1)这个记录放进map，这个记录的意义是如果任何一个数也不加时，累加和为0，这样，从0位置开始的子数组就被我们考虑到了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int maxLen(int[] arr, int k){
    if(arr==null || arr.length==0){
        return 0;
    }
    HashMap<Integer, Integer> map = new HashMap<>();
    map.put(0,-1)
    int sum = 0;
    int len = 0;
    for(int i=0;i<arr.length;i++){
        sum += arr[i];
        if(map.containsKey(sum-k)){
            len = Math.max(i-map.get(sum-k), len);
        }
        if(!map.containsKey(sum)){
            map.put(sum, i);
        }
    }
    return len;
}

给定一个无序数组arr，其中元素可正可负可0，求arr中所有的子数组中正数与负数个数相等的最长子数组长度

》方法一：
如果遍历到arr[i],0到i中的正数为x个，负数为y个，若0到j中的正数为x1个，负数为y1个。假设arr[j+1..i]之间的正数与负数相等。则有x-x1=y-y1，故有x-y=x1-y1。因此如果遍历到arr[i]处，找到最前面也满足正数-负数=x-y的位置即可。
因此，用一个HashMap，key为x-y，value为第一次出现该key的位置，遍历到arr[i]，如果map中有x-y，则len=max（i-map.get(x-y), len）如果没有key，则说明是第一次出现key，则把key和i放入map中

》方法二：
用第一道题的方法，先把数组arr中的正数全变成1，负数全变成-1，0不变，然后求累加和为0的最长子数组长度即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int maxLen2(int[] arr){
    int pos = 0;  //正数个数
    int nag = 0;  //负数个数
    int len = 0;
    HashMap<Integer, Integer> map = new HashMap<>();
    map.put(0, -1); //没有数字时，看作正负个数相等，位置为-1
    for(int i=0;i<arr.length;i++){
        if(arr[i]>0) pos++;
        else if(arr[i]<0) nag++;
        if(map.containsKey(pos-nag)){
            len = Math.max(i-map.get(pos-nag), len);
        }else{
            map.put(pos-nag, i);
        }
    }
    return len;
}

给定一个无序数组arr，其中元素只是1或0，求arr所有子数组中0和1个数相等的最长子数组长度。

》方法一：
核心思想和上题一样，只不过把记录正负换成记录1和0
》方法二：
用第一道题的方法，先把数组arr中的0全变成-1，1不变，然后求累加和为0的最长子数组长度即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int maxLen3(int[] arr){
    int one = 0;  //正数个数
    int zero = 0;  //负数个数
    int len = 0;
    HashMap<Integer, Integer> map = new HashMap<>();
    map.put(0, -1); //没有数字时，看作1和0个数相等，位置为-1
    for(int i=0;i<arr.length;i++){
        if(arr[i]==1) one++;
        else zero++;
        if(map.containsKey(one-zero)){
            len = Math.max(i-map.get(one-zero), len);
        }else{
            map.put(one-zero, i);
        }
    }
    return len;
}