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.

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?

The idea follows the similar solution as we did for Query Sum. We use a map, the key is the sum we get from index 0 to index i, and the value is index i. If we find sum - k is also in the map, we know there exists a subarray with sum k, and we compare it with the previous result.

public int maxSubArrayLen(int[] nums, int k) {
        int len = nums.length;
        if (len == 0) {
            return 0;
        }
        Map<integer, integer> sumMap = new HashMap<>();
        int sum = 0;
        int maxLen = 0;
        for (int i = 0; i < len; i++) {
            sum += nums[i];
            sumMap.put(sum, i);
            if (sumMap.containsKey(sum - k)) {
                int index = sumMap.get(sum - k);
                maxLen = Math.max(maxLen, i - index);
            }
        }
        return maxLen;
    }