LeetCode 325 Maximum Size Subarray Sum Equals k

LeetCode

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:

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.

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>`

题目大意：

最长子数组和等于k，求长度

解题思路：

一开始以为类似于LeetCode 209 Minimum Size Subarray Sum用同向双指针。但这题不是连续，因为此题含负数，不会连续大于等于target。考虑用presum的two sum法。

解题步骤：

N/A

注意事项：

1. 加入presum[0] = 0，因为这样才可以得到以首元素开始的子数组和
2. 若presum已经在hashmap中了，不要加入，因为要保证最长数组，如 [-1, 1], target = 0, index可以为0, 2
3. max_len答案只要初始化为0，不用最小值，因为最大长度必为非负

Python代码：

# 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)