## 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 entirenumsarray 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?

Thoughts:

1. Have a prefix sum record
2. Use hashtable to record the smallest index for the same sum
``````class Solution(object):
def maxSubArrayLen(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: int
"""
preSum, end, s, ans =, {}, 0 , 0
for i, num in enumerate(nums):
s += num
preSum.append(s)

# prepreSum[i]: sum of nums[0...i] exslusive i
ans = 0
for i, preS in enumerate(preSum):
if preS - k in end:
ans = max(ans, i - end[preS - k])
if preS not in end: #keep smaller
end[preS] = i

return ans
``````