560. 和为 K 的子数组

560. 和为 K 的子数组 #

链接 #

560. 和为 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

解答 #

方法：使用哈希表和前缀和

  1. 初始化：创建一个哈希表 HashMap，用于存储前缀和及其出现的次数。初始时，前缀和为 0 出现的次数为 1（即一个空数组）。另外，定义一个变量 count 用于计数和为 K 的子数组的数量，初始为 0。
  2. 计算前缀和：遍历数组，计算当前的前缀和 currentSum。对于每个 currentSum，检查 currentSum - K 是否在哈希表中。如果在，说明我们找到了一个和为 K 的子数组。
  3. 更新计数和哈希表：如果 currentSum - K 存在于哈希表中，将 count 增加 currentSum - K 在哈希表中的次数。然后，将 currentSum 的次数在哈希表中加 1。
  4. 返回结果：遍历完成后，返回 count 作为和为 K 的子数组的数量。
from typing import List
def subarraySum(nums: List[int], k: int) -> int:
    # 初始化哈希表和计数器
    prefix_sum_count = {0: 1}
    current_sum = 0
    count = 0
    
    # 遍历数组
    for num in nums:
        current_sum += num
        if current_sum - k in prefix_sum_count:
            count += prefix_sum_count[current_sum - k]
        prefix_sum_count[current_sum] = prefix_sum_count.get(current_sum, 0) + 1
    
    return count

例子：

[1, 2, 3, 0, 2] 和 k = 3：

  • 初始化哈希表为 {0: 1}，curSum = 0，count = 0。
  • 遍历数组：
    • curSum = 1，curSum - k = -2 不在哈希表中，哈希表为 {0: 1, 1: 1}。
    • curSum = 3，curSum - k = 0 在哈希表中，count += 1，哈希表为 {0: 1, 1: 1, 3: 1}。
    • curSum = 6，curSum - k = 3 在哈希表中，count += 1，哈希表为 {0: 1, 1: 1, 3: 1, 6: 1}。
    • curSum = 6，curSum - k = 3 在哈希表中，count += 1，哈希表为 {0: 1, 1: 1, 3: 1, 6: 2}。
    • curSum = 8，curSum - k = 5 不在哈希表中，哈希表为 {0: 1, 1: 1, 3: 1, 6: 2, 8: 1}。

PS：currentSum - K 存在于哈希表中，说明我们找到了一个和为 K 的子数组。如果不能理解请看下面的解释：

当我们遍历数组并计算当前的前缀和 currentSum 时，如果 currentSum - K 已经存在于哈希表中，这意味着我们在之前某个位置有一个前缀和，它与当前的前缀和之差正好是 K。 这里的关键在于理解前缀和的概念。前缀和数组 prefixSum 的第 i 个元素表示原数组从第一个元素到第 i 个元素的和。如果我们有两个前缀和 prefixSum[j] 和 prefixSum[i]（其中 j < i），那么数组中从第 j+1 个元素到第 i 个元素的和可以通过计算 prefixSum[i] - prefixSum[j] 得到。 因此，当我们发现 currentSum - K 在哈希表中时，我们可以推断出在数组中存在一个从某个位置 m 到当前位置的子数组，其和为 K。这是因为：

  • currentSum 是从数组开始到当前位置的所有元素的和。
  • currentSum - K 是从数组开始到某个位置 m 的所有元素的和（m 是 currentSum - K 在哈希表中对应的位置）。 所以，currentSum - (currentSum - K) = K，这意味着从位置 m+1 到当前位置的子数组元素和为 K。 哈希表帮助我们快速查找是否存在这样的 currentSum - K，而不需要遍历整个数组来计算每个可能的子数组的和。这就是为什么 currentSum - K 存在于哈希表中时，我们可以确定找到了一个和为 K 的子数组。
Edit Edit this page