560_和为K的子数组

类型：数组

1. 和为K的子数组 💛 ⭐
https://leetcode-cn.com/problems/subarray-sum-equals-k/

❓ 找到整数数组中和为 k 的连续子数组的个数。

输入: nums = [1,1,1], k = 2 输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。

💡 枚举

考虑以 i 为结尾的连续子数组。我们需要统计符合条件的下标 j 的个数，其中 0 ≤ j ≤ i，且子数组 [j, i] 的和恰好为 k。子数组 [j, i] 的和可以通过子数组 [j + 1, i] 的和推算出。

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

💡 前缀和 + 哈希

枚举方法的瓶颈在于，对于每一个 i，我们需要枚举所有的 j 来判断是否符合条件。我们可以对此进行优化。

定义 pre[i] 表示子数组 [0, i] 之和。显然，pre[i] = pre[i - 1] + nums[i]。

要求子数组 [j, i] 之和为 k，那么 pre[i] - pre[j - 1] = k，即 pre[j - 1] = pre[i] -k

那么我们要求以 i 为结尾的和为 k 的连续子数组，只需要统计有多少个前缀和为 pre[i] - k 的 pre[j] 即可。对此我们建立哈希表，以和为键，以出现次数为值。从左往右边更新哈希表边计算答案。
```
class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        ans = 0
        mp = {}
        pre_sum = 0
        for j in range(len(nums)):
            if pre_sum in mp:
                mp[pre_sum] += 1
            else:
                mp[pre_sum] = 1
            pre_sum += nums[j]
            if pre_sum - k in mp:
                ans += mp[pre_sum - k]
        return ans
```
时间复杂度：O(n)，空间复杂度：O(n)