# 325. Maximum Size Subarray Sum Equals k

Question link is here.

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

Example 1:

Input: nums = [1,-1,5,-2,3], k = 3
Output: 4
Explanation: The subarray [1, -1, 5, -2] sums to 3 and is the longest.

Example 2:

Input: nums = [-2,-1,2,1], k = 1
Output: 2
Explanation: The subarray [-1, 2] sums to 1 and is the longest.

# Solution

The question asks us to find the longest subarray with sum equals k. Let sub(i, j) denote that the sum of the subarray starts at i and ends at j.

So we know sub(i,k) + sub(k+1, j) = sub(i,j).

At this point, we only to track sub(0, j) while we go through the array. And each time we just need to check if there exists some index t, that sub(0, j) - sub(0, t) = k. And to make the query of sub(i, j) more quickly, We would to use the hashmap<sub(0, i), j> to store the sum we already calculated.

We need to pay attention that we don't need to update value for already exist keys, since we need to get the longest subarray.

The code is shown below.

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

Time complexity: $O(n)$

Space Complexity: $O(n)$