Maximum Size Subarray Sum Equals k

lc 325

Given an array nums and a target value k, find the maximum length of a subarray that sums to k. If there isn't one, return 0 instead.

Note: The sum of the entire nums array is guaranteed to fit within the 32-bit signed integer range.

Example 1: Given nums = [1, -1, 5, -2, 3], k = 3, return 4. (because the subarray [1, -1, 5, -2] sums to 3 and is the longest)

Example 2: Given nums = [-2, -1, 2, 1], k = 1, return 2. (because the subarray [-1, 2] sums to 1 and is the longest)

Follow Up: Can you do it in O(n) time? https://discuss.leetcode.com/topic/33537/java-o-n-explain-how-i-come-up-with-this-idea/2

注意要map要put（0，1） 可以看lc303

public class Solution {
    public int maxSubArrayLen(int[] nums, int k) {
        if(nums == null || nums.length == 0) return 0;
        int res = 0;
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int i = 1; i < nums.length; i++){
            nums[i] += nums[i - 1];
        }
        map.put(0, -1);
        for (int i = 0; i < nums.length; i++){
            if(map.containsKey(nums[i] - k)){
              res = Math.max(i - map.get(nums[i] - k)  , res);  
            }
           if (!map.containsKey(nums[i])) {// keep only 1st duplicate as we want first index as left as possible
                map.put(nums[i], i);
            }
}
        return res;

    }
}

public class NumArray { int[] sum;

public NumArray(int[] nums) {
    if(nums == null || nums.length == 0) return;
    sum = new int[nums.length];
    sum[0] = nums[0];
    for(int i = 1; i < nums.length; i++){
        sum[i] = sum[i - 1] + nums[i];
    }
}

public int sumRange(int i, int j) {
    if( i > j || i > sum.length || j > sum.length) return 0;
    if(i == 0 ) return sum[j];
    return sum[j] - sum[i - 1];
}

}

// Your NumArray object will be instantiated and called as such: // NumArray numArray = new NumArray(nums); // numArray.sumRange(0, 1); // numArray.sumRange(1, 2); ```