LeetCode 560 Subarray Sum Equals K

LeetCode

Given an array of integers nums and an integer k, return the total number of continuous subarrays whose sum equals to k.

Example 1:

Input: nums = [1,1,1], k = 2
Output: 2

Example 2:

Input: nums = [1,2,3], k = 3
Output: 2

Constraints:

`1 <= nums.length <= 2 10<sup>4</sup>*-1000 <= nums[i] <= 1000*-10<sup>7</sup> <= k <= 10<sup>7</sup>`

题目大意：

子数组和等于k的个数

解题思路：

子数组和第一时间想到presum，而数组元素之间关系也应该想到two sum

解题步骤：

N/A

注意事项：

1. 加0到presum中或者加0到sum_to_idx字典中，确保presum本身可以等于k
2. 数组含负数，也即是presum中可以含有多个相同的值，所以sum_to_idx要转成频数而不是下标。如[-1, 1, -1, 1], k=0结果为4，而不是3, 容易漏整个数组和

Python代码：

# presum = [0, 1, 2, 3], target = presum[i] - k = presum[j]
# add 0 to presum so that presum[i] = k
# [0, -1, 0, -1, 0]
# [0, 1]
def subarraySum(self, nums: List[int], k: int) -> int:
	presum, res = [0], 0 #
	for n in nums:
		presum.append(presum[-1] + n) # 0, 1, 2, 3
	sum_to_idx = collections.defaultdict(int)
	for i in range(len(presum)): #
		if presum[i] - k in sum_to_idx: # 1-1
			res += sum_to_idx[presum[i] - k] #4
		sum_to_idx[presum[i]] += 1 # {0:2, -1:2, 2:2}
	return res

算法分析：

时间复杂度为O(n)，空间复杂度O(n)