<div>
Given an integer array nums and an integer k, return the maximum length of a subarray that sums to k. If there is not one, return 0 instead.
Example 1:
<pre>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. </pre>
Example 2:
<pre>Input: nums = [-2,-1,2,1], k = 1 Output: 2 Explanation: The subarray [-1, 2] sums to 1 and is the longest. </pre>
Constraints:
1 <= nums.length <= 2 * 10<sup>5</sup>-10<sup>4</sup> <= nums[i] <= 10<sup>4</sup>-10<sup>9</sup> <= k <= 10<sup>9</sup>
</div>
题目大意：
最长子数组和等于k，求长度
解题思路：
一开始以为类似于LeetCode 209 Minimum Size Subarray Sum用同向双指针。但这题不是连续，因为此题含负数，不会连续大于等于target。考虑用presum的two sum法。
解题步骤：
N/A
注意事项：
- 加入presum[0] = 0，因为这样才可以得到以首元素开始的子数组和
- 若presum已经在hashmap中了，不要加入，因为要保证最长数组，如 [-1, 1], target = 0, index可以为0, 2
- max_len答案只要初始化为0，不用最小值，因为最大长度必为非负
Python代码：
1
2
3
4
5
6
7
8
9
10
11
12# presum[i] - presum[j] = k
def maxSubArrayLen(self, nums: List[int], k: int) -> int:
max_len, presum = 0, 0 # not float('-inf')
sum_to_idx = collections.defaultdict(int)
sum_to_idx[0] = 0
for i in range(len(nums)):
presum += nums[i]
if presum - k in sum_to_idx:
max_len = max(max_len, i - sum_to_idx[presum - k] + 1)
if presum not in sum_to_idx: # remember
sum_to_idx[presum] = i + 1
return max_len
算法分析：
时间复杂度为O(n)，空间复杂度O(n)
