2020-05-26

## 325. Maximum Size Subarray Sum Equals k

### Question:

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:

``````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.
``````

Can you do it in O(n) time?

### Solution:

Using the similar idea as LeetCode Question 525, we need to use hash table to record the first sum value and its corresponding index. Then if the hash table has the difference between current sum and k, we compare with the result to find the maximum value.

``````class Solution {
public int maxSubArrayLen(int[] nums, int k) {
if (nums == null || nums.length == 0) return 0;
int result = 0;
int sum = 0;

HashMap<Integer, Integer> map = new HashMap<>();

map.put(0,-1);

for (int i = 0; i < nums.length; i++) {
sum += nums[i];
if (map.containsKey(sum - k)) {
result = Math.max(result, i - map.get(sum - k));
}
if (!map.containsKey(sum)) {
map.put(sum, i);
}
}
return result;
}
}
``````