325. Maximum Size Subarray Sum Equals k

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,
return4. (because the subarray[1, -1, 5, -2]sums to 3 and is the longest)

Example 2:

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

Follow Up:
Can you do it in O(n) time?

Solution:

Using hash map with key = sum value from 0 to current position - 1, value = current position

• Go through the whole array,
  • calculate the current sum, and find the target value sum - k
    • if target is in the map ---> from 0 to x in previous array we have a sum == target
      • calculate the length (current index i - (x + 1)), update max length
  • if(current sum) not in the map, update the map
  • else if current sum in the map ---> previous we have the same sum ----> in order to get maximum length, not update the map
• Note:
  • this question is different from sliding window problem which we use two pointers to solve
    • sliding window: all elements > 0 && find range >=s
    • this problem: find exactly value ---> hash map

public int maxSubArrayLen(int[] nums, int k) {
        Map<Integer, Integer> hm = new HashMap<>();
        int sum = 0;
        int max = -1;
        hm.put(0,0);
        for(int i = 1; i < nums.length + 1; i++){
            sum += nums[i-1];
            int target = sum - k;
            if(hm.containsKey(target)){
                max = Math.max(max, i - hm.get(target));  
            }

            if(!hm.containsKey(sum)){
                hm.put(sum, i);
            }
        }
        if(max == -1){
            return 0;
        }else{
            return max;
        }
    }

Reference:

https://segmentfault.com/a/1190000005771068