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,
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 time?
Solution: Prefix Sum
class Solution(object):
def maxSubArrayLen(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: int
"""
max_len = 0
pre_sum = 0
sums = {0: -1}
for idx, num in enumerate(nums):
pre_sum += num
if pre_sum - k in sums:
max_len = max(max_len, idx - sums[pre_sum - k])
if pre_sum not in sums:
sums[pre_sum] = idx
return max_len