CodeCollection2018
8/22/2019 - 8:17 AM

Maximum Size Subarray Sum Equals k（和为k的最长连续子数组）

这里的子数组是连续的，给定一个数组arr和目标值k，求解数组中所有连续子数组之和等于k的最大长度的子数组的长度，时间复杂度是O(n)

n2
content_copyfile_download
public int maxLenSumToK_NoMap(int [] nums,int k){
    int len = nums.length;
    int [] sums = new int[len];
    sums[0] = nums[0];
    for(int i=1; i < len; i++){
        sums[i] = sums[i-1]+nums[i];  //先从第一个往后累加
    }
    int max = Integer.MIN_VALUE;
    for(int i = 0; i < len; i++){
        for(int j = i; j < len; j++){
            if(sums[j]-sums[i]==k) max = Math.max(max,j-i); //判断所有的子数组之和等不等于k，并记录最大长度子数组
        }
    }
}
n
content_copyfile_download
public int maxLenSumToK_WithMap(int [] nums,int k){
    int len = nums.length;
    int [] sums = new int[len];
    sums[0]=nums[0];
    int max = Integer.MIN_VALUE;
    for(int i = 1 ; i < len; i++){
        sums[i] = sums[i-1]+nums[i];
    }
    Map<Integer,Integer> map = new HashMap<>();  //用map来保存累加值和下表索引之间的对应关系
    for(int i = 0; i < len; i++){
        int dis = sums[i]-k;//求当前累加值和k之间的差距
        int j = map.get(dis);  //去map中查找有没有已经放入了这个期待的差距值，有的话拿到其索引值用于更新max值
        if(j!=null) max = Math.max(max,j-i);  //更新max
        if(!map.get(sums[i])) map.put(sums[i],i); //如果没有该累加值则加入，如果有的话放入的是前面的因为这样可以max更大。
    }
    return max;
}