LeetCode-560. 和为 K 的子数组【数组 哈希表 前缀和】

题目描述：

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。

子数组是数组中元素的连续非空序列。

示例 1：

输入：nums = [1,1,1], k = 2
输出：2
示例 2：

输入：nums = [1,2,3], k = 3
输出：2

提示：

1 <= nums.length <= 2 * 10⁴
-1000 <= nums[i] <= 1000
-10⁷ <= k <= 10⁷

解题思路一：一边算前缀和一边统计。这里用哈希表统计前缀和出现的次数，那么和为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)