和为k的子数组

1、题目

image-20240229220749386

2、题解

前缀和+哈希表

前缀和：一个数组的某个下标之前的所有数组元素的和（包含自身）

通常会习惯在前缀和首位放一个0，例如数组\([1,2,3]\),前缀和就为\([0,1,3,6]\)，前缀和有助于快速计算某个区间内的和，例如要计算\(i,j\)之间的和：\(nums[i]+nums[i+1]+……+nums[j]\),可以看作是\(nums[0]+nums[1]+……+nums[i]+……+nums[j]\)减去\(nums[0]+nums[1]+……+nums[i-1]\),也可以看作\(preSum[j]-preSum[i-1]\)。

在遍历过程中，统计历史中每一个前缀和出现的次数，然后计算到i位置的前缀和\(presum\)减去目标k在遍历过程中出现的次数，假设出现\(m\)次，代表第i位以前有\(m\)个连续子数组的和为\(presum-k\)，这\(m\)个和为\(presum-k\)的连续子数组，每一个都可以和\(presum\)组合成\(presum-(presum-k)=k\).

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

        preSums[0]=1

        presums = 0 

        for i in range(nums_len):
            presums +=nums[i]

            count += preSums[presums-k]

            preSums[presums] += 1

        return count