LeetCode325.最大子数组之和为k

题目链接：LeetCode325

这道题暴力很好做，但是找技巧确实不好想，首先假设这么一个场景，从下标为0到下标为100，和sum = 2000，假设我们要求的目标k=800，那么我们只要知道从0开始，最早出现的下标i，使得0到i之间的和为1200，这样就能保证i+1到1000的和为800，同时还能保证这个长度是以1000结尾的最大的长度

建立一个Map，key存放的是和，value存放的是第一次出现该和的下标，后面如果再出现直接跳过。

class Solution {
    public static int maxLength(int[] arr,int aim) {
        if(arr == null || arr.length == 0)
            return 0;
        HashMap<Integer,Integer> map = new HashMap<>();
        map.put(0,-1);
        int len = 0;
        int sum = 0;
        for(int i = 0;i < arr.length;i++) {
            sum += arr[i];
            if(map.containsKey(sum - aim))
                len = Math.max(i - map.get(sum - aim),len);
            if(!map.containsKey(sum))
                map.put(sum,i);
        }
        return len;
    }
}

总结

很多类似的变形题，比方说，一个数组中有奇数有偶数，求奇数和偶数个数相等的最长子数组的长度，这个就把奇数看作1，把偶数看作-1，求和为0的最长子数组的长度；再比方说，一个数组中有0,1,2，求0,1,2个数相等的最长子数组的长度，也是一样的，0还是0，把1看成1，2看成-1，最终叶转换为求和为0的最长子数组的长度。