【哈希表】Leecode-560. 和为 K 的子数组

【题目】

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

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

示例 1：

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

示例 2：

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

【题解】

题解1：

• 思路

        遍历数组，遍历过程中，我们统计历史中每一个前缀和出现的个数，然后计算到当前位置的前缀和$presum$减去目标k在历史上出现过几次，count累加

• 复杂度

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

• 代码

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        count = 0
        dict_pre = collections.defaultdict(int)
        dict_pre[0] = 1
        n = len(nums)
        presum = 0

        for i in range(n):
            presum += nums[i]
            count += dict_pre[presum-k]
            dict_pre[presum] += 1
        return count