python每日一题——10合为k的子数组

题目

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

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

示例 1：

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

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

答案

以下是给定整数数组 nums 和整数 k，统计并返回该数组中和为 k 的子数组的个数的 Python 代码：

def subarray_sum(nums, k):
    count = 0  # 记录符合条件的子数组个数
    prefix_sum = {}  # 前缀和的哈希表，用于记录前缀和出现的次数
    prefix_sum[0] = 1  # 初始化前缀和为 0 的次数为 1
    cur_sum = 0  # 记录当前的前缀和

    for num in nums:
        cur_sum += num  # 累加当前元素到前缀和
        # 查找是否存在前缀和 cur_sum - k 在哈希表中，若存在则说明存在一个和为 k 的子数组
        count += prefix_sum.get(cur_sum - k, 0)
        # 将当前前缀和 cur_sum 加入哈希表，更新出现次数
        prefix_sum[cur_sum] = prefix_sum.get(cur_sum, 0) + 1

    return count

注释说明：

• count 记录符合条件的子数组个数。
• prefix_sum 是前缀和的哈希表，用于记录前缀和出现的次数。初始化时将前缀和为 0 的次数设为 1。
• cur_sum 记录当前的前缀和。
• 遍历 nums 数组中的每个元素，将其累加到 cur_sum 中。
• 在 prefix_sum 中查找是否存在前缀和 cur_sum - k，若存在则说明存在一个和为 k 的子数组，将对应的计数加到 count 中。这里使用 get 方法来获取哈希表中指定键的值，若键不存在则返回默认值 0。
• 将当前前缀和 cur_sum 加入到 prefix_sum 中，更新出现次数。若键已存在则将其出现次数加一，否则设为 1。同样使用 get 方法来获取哈希表中指定键的值，若键不存在则返回默认值 0。
• 最后返回 count，即符合条件的子数组个数。