LeetCode-560. 和为 K 的子数组【数组 哈希表 前缀和】
- 题目描述：
- 解题思路一：一边算前缀和一边统计。这里用哈希表统计前缀和出现的次数，那么和为k的子数组的个数就是当前前缀和-k的个数，即preSums[presum - k]。画个图表述就是：
- 解题思路二：
- 解题思路三：
题目描述：
给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。
子数组是数组中元素的连续非空序列。
示例 1：
输入：nums = [1,1,1], k = 2
输出：2
示例 2：
输入：nums = [1,2,3], k = 3
输出：2
提示：
1 <= nums.length <= 2 * 104
-1000 <= nums[i] <= 1000
-107 <= k <= 107
解题思路一：一边算前缀和一边统计。这里用哈希表统计前缀和出现的次数，那么和为k的子数组的个数就是当前前缀和-k的个数，即preSums[presum - k]。画个图表述就是：
红色的是当前遍历到的前缀和presum，假如他之前有两个前缀和等于presum−k（蓝色范围），那么很明显，就会有两个连续子数组的和为k，对应图中橙色范围。
【这里利用了collections.defaultdict(int)的特性，可以直接赋值，并且不存在的key对应的value为0】
class Solution:
def subarraySum(self, nums: List[int], k: int) -> int:
count = 0
n = len(nums)
preSums = collections.defaultdict(int)
preSums[0] = 1 # 这个初始化很重要
presum = 0
for i in range(n):
presum += nums[i]
count += preSums[presum - k] # 利用defaultdict的特性，当presum-k不存在时，返回的是0。这样避免了判断
preSums[presum] += 1 # 给前缀和为presum的个数加1
return count
时间复杂度：O(n)
空间复杂度：O(n)
很巧妙！
解题思路二：
时间复杂度：O(n)
空间复杂度：O(n)
解题思路三：
时间复杂度：O(n)
空间复杂度：O(n)
