统计和为 K 的子数组个数

统计和为 K 的子数组个数

问题背景

LeetCode 560. 和为 K 的子数组个数
给定一个整数数组 nums 和一个整数 k，需要统计并返回数组中和为 k 的连续子数组的个数。

相关知识

在解决这个问题之前，我们需要了解一些相关知识点。

子数组

子数组是指数组中元素的连续非空序列。例如，对于数组 [1, 2, 3]，它的子数组包括 [1]、[2]、[3]、[1, 2]、[2, 3] 和 [1, 2, 3]。

问题介绍

给定一个整数数组 nums 和一个整数 k，找出数组中和为 k 的连续子数组的个数。

解题思路

解决这个问题的一种常用方法是使用前缀和和哈希表。

具体步骤如下：

1. 初始化两个变量 ans 和 sum，分别用于存储答案和当前子数组的和。
2. 初始化一个哈希表 dic，用于存储前缀和及其出现的次数。首先在哈希表中添加一对键值对 (0, 1)，表示前缀和为 0 出现了 1 次。
3. 遍历数组 nums，计算当前子数组的和 sum，并统计前缀和为 sum - k 的次数。如果前缀和为 sum - k 在哈希表 dic 中已经存在，说明存在一个子数组的和为 k。
4. 更新哈希表 dic，将当前前缀和 sum 的次数加 1。
5. 继续遍历数组，重复步骤 3 和步骤 4 直到遍历完整个数组。

最终，ans 中存储的就是和为 k 的连续子数组的个数。

代码实现

下面是 Python 代码的实现，包括注释说明：

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        if nums is None or len(nums) == 0:
            return 0
        
        n = len(nums)
        ans = 0

        # 初始化前缀和为 0 出现了 1 次
        sum = 0
        dic = {0: 1}

        for i in range(n):
            sum += nums[i]
            # 统计前缀和为 sum - k 的次数
            ans += dic.get(sum - k, 0)
            # 更新前缀和的次数
            dic[sum] = dic.get(sum, 0) + 1
            
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

时间和空间复杂度

• 时间复杂度：遍历一次数组，时间复杂度为 O(n)，其中 n 是数组 nums 的长度。
• 空间复杂度：哈希表 dic 最多存储 n 个前缀和，因此空间复杂度为 O(n)。

结论

统计和为 K 的子数组个数是一个常见的数组处理问题。本文介绍了解决该问题的方法，并提供了详细的代码实现和注释说明。希望本文对理解该问题的解决思路和实现有所帮助。