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.

Follow Up: 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 , 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