Problem

Given an arraynumsand a target valuek, find the maximum length of a subarray that sums tok. 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:

Givennums=[1, -1, 5, -2, 3],k=3,
return4. (because the subarray[1, -1, 5, -2]sums to 3 and is the longest)

Example 2:

Givennums=[-2, -1, 2, 1],k=1,
return2. (because the subarray[-1, 2]sums to 1 and is the longest)

Follow Up:
Can you do it in O(n) time?

Solution:

1. prefix sum everything from index to 0 to every index. Totaling length n + 1. Call it S.
2. Subarray sum from index l to index r will be S[r] - S[l]. Thus we aim to find S[r] - S[l] = key where "r - l" is max
   1. To accomplish in O(n) time, it means we need to find out the result in one pass or countable number
   2. Thus, we need a hashmap to store previous results.
   3. Map<k+S[i], i> , thus, if result S[j]== k + S[i] comes along, we can get ONE result of j - i
   4. Note we want to preserve the earliest occurrence of every k + S[i], such that when S[j] == k + S[i] happens, j - i will be largest
3. return

Python:

def maxSubArrayLen(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        n = len(nums)
        preSum = [0] + nums[:]
        resLen = 0
        dic = {}  # key is "target + prefix Sum [i]", value is index,i,
        dic[k + preSum[0]] = 0

        for i in range(1, 1 + n):
            preSum[i] = preSum[i-1] + nums[i-1]

            if preSum[i] in dic:
                resLen = max(resLen, i - dic[preSum[i]])

            if k + preSum[i] not in dic:
                dic[k+preSum[i]] = i

        return resLen

Time: O(n)

Space: O(n)