560. 和为 K 的子数组(中等）-子串

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

分析

• 需要想到累计和，还有能边遍历边计算，当发生累计和以及累计和减去k的值也在字典中时开始计算
• 注意陷阱，就是开始需要初始化一个累计和为0的个数为1
• 并且是要用字典记录，key是累计和，value是对应的个数

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        # 计算累计和
        # 边走边计算对应的sum_all -k 是否已经存在，并且需要用字典记录，而不是集合，因为前面有可能有多个相同的sum_all
        sum_to_count = {}
        # 重大陷阱，需要定义sum为0时值为1，因为有可能包含第一个元素，这样也需要有个被减数
        sum_to_count[0] = 1
        n = len(nums)
        sum_all = 0
        res = 0
        for n in nums:
            sum_all += n
            if sum_all - k in sum_to_count:
                res += sum_to_count[sum_all - k]
            
            if sum_all in sum_to_count:
                sum_to_count[sum_all] += 1
            else:
                sum_to_count[sum_all] = 1
        
        return res