<div>
Given an array of integers nums and an integer k, return the total number of continuous subarrays whose sum equals to k.
Example 1:
<pre>Input: nums = [1,1,1], k = 2 Output: 2 </pre>
Example 2:
<pre>Input: nums = [1,2,3], k = 3 Output: 2 </pre>
Constraints:
1 <= nums.length <= 2 * 10<sup>4</sup>-1000 <= nums[i] <= 1000-10<sup>7</sup> <= k <= 10<sup>7</sup>
</div>
题目大意：
子数组和等于k的个数
解题思路：
子数组和第一时间想到presum，而数组元素之间关系也应该想到two sum
解题步骤：
N/A
注意事项：
- 加0到presum中或者加0到sum_to_idx字典中，确保presum本身可以等于k
- 数组含负数，也即是presum中可以含有多个相同的值，所以sum_to_idx要转成频数而不是下标。如[-1, 1, -1, 1], k=0结果为4，而不是3, 容易漏整个数组和
Python代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14# 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)
