MENU

LeetCode325.最大子数组之和为k

August 22, 2018 • Read: 193 • LeetCode

题目链接: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的最长子数组的长度。

Archives Tip
QR Code for this page
Tipping QR Code