7、 和为 K 的子数组

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

子数组是数组中元素的连续非空序列。

示例 1：

输入：nums = [1,1,1], k = 2
输出：2

示例 2：

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

提示：

• 1 <= nums.length <= 2 * 104
• -1000 <= nums[i] <= 1000
• -107 <= k <= 107

      function subarraySum(nums = [], k) {
        let sum = 0;
        const map = new Map([[0, 1]]);
        return nums.reduce((res, num) => {
          sum += num;
          res += map.get(sum - k) ?? 0;
          map.set(sum,(map.get(sum) ?? 0)+1)
          return res;
        }, 0);
      }

前缀和的概念

前缀和 pre_sum[i] 表示从数组开始位置到第 i 个元素的累加和。即：

pre_sum[i]=nums[0]+nums[1]+…+nums[i]pre\_sum[i] = nums[0] + nums[1] + \ldots + nums[i]pre_sum[i]=nums[0]+nums[1]+…+nums[i]

前缀和的性质

如果我们有两个前缀和 pre_sum[i] 和 pre_sum[j]（其中 i < j），那么从位置 i+1 到位置 j 的子数组的和就是：

nums[i+1]+nums[i+2]+…+nums[j]=pre_sum[j]−pre_sum[i]nums[i+1] + nums[i+2] + \ldots + nums[j] = pre\_sum[j] – pre\_sum[i]nums[i+1]+nums[i+2]+…+nums[j]=pre_sum[j]−pre_sum[i]

算法的原理

给定一个目标和 k，我们希望找到一个子数组 nums[i+1..j]，其和为 k。利用前缀和的性质，如果存在某个前缀和 pre_sum[i] 使得：

pre_sum[j]−pre_sum[i]=kpre\_sum[j] – pre\_sum[i] = kpre_sum[j]−pre_sum[i]=k

那么这个子数组 nums[i+1..j] 的和就是 k。

举例说明

让我们用具体的数字来解释这个过程。假设 nums = [1, 2, 3]，目标和 k = 3。

1. 前缀和的计算：
   • 对于第一个元素 1：pre_sum[0] = 1
   • 对于第二个元素 2：pre_sum[1] = 1 + 2 = 3
   • 对于第三个元素 3：pre_sum[2] = 1 + 2 + 3 = 6
2. 查找符合条件的子数组：我们遍历数组并维护一个哈希表 map 来记录每个前缀和出现的次数：
   • 初始时：map = {0: 1}（表示前缀和为 0 的情况，即在数组开始之前）
   • 遍历第一个元素 1：
     • 当前前缀和：pre_sum = 1
     • 更新哈希表：map = {0: 1, 1: 1}
   • 遍历第二个元素 2：
     • 当前前缀和：pre_sum = 3
     • 更新哈希表：map = {0: 1, 1: 1, 3: 1}
     • 检查 pre_sum - k = 3 - 3 = 0 是否在 map 中：
       • map[0] = 1，表示从数组开始到当前位置的子数组 [1, 2] 的和为 3，因此找到一个子数组 [1, 2] 满足条件。
   • 遍历第三个元素 3：
     • 当前前缀和：pre_sum = 6
     • 更新哈希表：map = {0: 1, 1: 1, 3: 1, 6: 1}
     • 检查 pre_sum - k = 6 - 3 = 3 是否在 map 中：
       • map[3] = 1，表示从某个位置到当前位置的子数组 [3] 的和为 3，具体来说是从第二个元素之后（即第三个元素开始）的子数组 [3] 的和为 3。

详细解释

在上面的例子中：

• pre_sum = 6 表示从数组开始到第三个元素的累加和。
• pre_sum - k = 6 - 3 = 3，我们发现 map[3] = 1。
• map[3] = 1 表示在第二个元素位置之前（前缀和 3）累加和为 3。

因此，当我们遇到 pre_sum = 6 并发现 pre_sum - k = 3 存在于 map 中，说明存在一个从第二个元素之后（即第三个元素开始）到当前元素的子数组 [3]，其和为 3。

总结

我们通过维护一个哈希表来记录每个前缀和出现的次数，并在遍历数组时检查 pre_sum - k 是否存在于哈希表中。如果存在，则说明存在一个子数组，其和为 k。这样可以高效地找到所有符合条件的子数组。如果考虑负数就可能出现某个前缀和出现多次的情况，所以需要一个hash表储存出现的次数，而不仅仅是+1