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 的最长子数组的长度。