题解 | #和为K的连续子数组#

public class Solution {
    /**
     * max length of the subarray sum = k
     * @param arr int整型一维数组 the array
     * @param k int整型 target
     * @return int整型
     */
    public int maxlenEqualK (int[] arr, int k) {
        // write code here
        int len = arr.length;
        if(arr == null || len == 0){
            return 0;
        }
        // key 从0加到i的sum和， 减k可能是负数，value值表示sum值最早出现的位置，
        //因为有正有负
        Map<Integer, Integer> map = new HashMap<Integer,Integer>();
        //sum-k存在，从map中取出sum-k对应的value，记为j，
        //得到s(i)-s(j)=k，所以此时arr[j+1, i]的长度即为题目要求的子数组的长度
        //包含j+1. 这样j+1 >= 1 如果不考虑0位置元素
        map.put(0,-1);
        int length = 0;
        int sum = 0;
        for(int i = 0;i< arr.length;i++){
            sum += arr[i];
            // sum 减去 sum -k == k ，所以看一下sum -k 位置的数有没有记录
            //有的话，取最大的连续子数组长度 长度就是 sum位置 i 减去 sum -k 位置的index 
            if(map.containsKey(sum - k)){
                length = Math.max(i - map.get(sum - k), length);
            }
            if(!map.containsKey(sum)){
                map.put(sum, i);
            }
        }
        return length;
    }
}