【前缀和】LeetCode 560. 和为k的字数组

**前缀和**
================在 LeetCode 上，第560 题是 "和为 k 的子数组"。这个问题要求我们找出给定整数数组中所有和为 k 的子数组的数量。

**问题描述**
-------------

给定一个整数数组 `nums` 和一个目标和 `k`，请返回和为 `k` 的子数组的数量。

**示例1**
--------

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

输出：`2`

解释：和为3 的子数组是 `[1,2]` 和 `[3]`。

**示例2**
--------

输入：`nums = [1,2,3,4], k =5`

输出：`2`

解释：和为5 的子数组是 `[1,4]` 和 `[2,3]`。

**解决方案**
------------我们可以使用前缀和来解决这个问题。前缀和是一个数组，其中每个元素是原始数组中所有小于或等于该元素的元素之和。

class Solution:
 def subarraySum(self, nums: List[int], k: int) -> int:
 # 初始化前缀和数组 prefix_sum = [0] * (len(nums) +1)
 # 计算前缀和 for i in range(len(nums)):
 prefix_sum[i +1] = prefix_sum[i] + nums[i]
 # 使用哈希表存储前缀和与目标和的差值 count = {0:1}
 res =0 # 遍历前缀和数组 for i in range(len(prefix_sum)):
 # 计算当前元素与目标和的差值 diff = prefix_sum[i] - k # 如果差值存在于哈希表中，则增加结果计数 if diff in count:
 res += count[diff]
 # 更新哈希表中的值 count[prefix_sum[i]] = count.get(prefix_sum[i],0) +1 return res

**注释**
--------

* 我们首先初始化一个前缀和数组 `prefix_sum`，其中每个元素是原始数组中所有小于或等于该元素的元素之和。
* 然后，我们计算前缀和数组中的值。我们使用一个循环来遍历原始数组，并将每个元素与前一个元素的和相加，以得到当前元素的前缀和。
* 接下来，我们使用哈希表 `count` 来存储前缀和与目标和的差值。我们初始化哈希表中的值为0，表示没有任何前缀和与目标和的差值。
* 然后，我们遍历前缀和数组，并计算当前元素与目标和的差值 `diff`。如果 `diff` 存在于哈希表中，则增加结果计数 `res`。我们使用 `get()` 方法来获取哈希表中的值，如果不存在则返回0。
* 最后，我们更新哈希表中的值，表示当前元素与目标和的差值。

**时间复杂度**
--------------

时间复杂度为 O(n)，其中 n 是原始数组的长度。我们使用一个循环来遍历原始数组，并计算前缀和数组中的值。

**空间复杂度**
------------空间复杂度为 O(n)。我们使用一个哈希表 `count` 来存储前缀和与目标和的差值，大小为 n。