LC 560和为 K 的子数组Subarray Sum Equals K　中等

统计数组中元素和恰好等于 k 的非空连续子数组的个数。

思路 前缀和 + 哈希表：累加前缀和 s，答案累加 cnt[s-k]，哈希表记录各前缀和出现次数。时间 O(n)。

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        cnt = defaultdict(int)
        cnt[0] = 1
        s = ans = 0
        for x in nums:
            s += x
            ans += cnt[s - k]
            cnt[s] += 1
        return ans