Maximum Size Subarray Sum Equals k

给一个arr, 求最大的size的subarray的和是k的.

这个题的简单版本是 Subarray Sum Equals K , 升级版本是 Minimum Operations to Reduce X to Zero

这个题的精髓是找到pre sum. 所以最初的版本code如下:

class Solution {
    public int maxSubArrayLen(int[] nums, int k) {
        int[] pre = new int[nums.length + 1];
        int res = 0;
        for(int i = 1; i < nums.length + 1; i++) {
            pre[i] = pre[i-1] + nums[i - 1];
        } 
        for(int i = 0; i < nums.length; i++) {
            for(int j = i + 1; j < nums.length + 1; j++) {
                if(pre[j] - pre[i] == k) {
                    res = Math.max(res, j - i);
                }
            }
        }
        return res;
    }
}

由pre[j] - pre[i] == k可以看出, 我们找的是2个数字的差等于k, 那么可以看成是2sum问题, 在2sum问题中, 用HashMap优化速度. 需要注意的是, 有可能同一个sum出现在很多个位置, 因为我们找的是max, 所以要找最开始的(最远)的i.

class Solution {
    public int maxSubArrayLen(int[] nums, int k) {
        int[] pre = new int[nums.length + 1];
        int res = 0;
        for(int i = 1; i < nums.length + 1; i++) {
            pre[i] = pre[i-1] + nums[i - 1];
        } 
        Map<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < nums.length + 1; i++) {
            if(map.containsKey(pre[i] - k)) {
                res = Math.max(res, i - map.get(pre[i] - k));
            }
            if(!map.containsKey(pre[i]))
                map.put(pre[i], i);
        }
        return res;
    }
}