560. 和为 K 的子数组 Medium

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

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

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

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

解题思路

输入：一个整数数组 nums，一个整数 k

输出：返回数组中和为 k 的子数组个数

本题属于哈希 + 前缀和问题。

我们需要维护以下三个变量：

• total：当前遍历位置的前缀和；
• count：满足条件的子数组个数；
• prefix_map：一个哈希表，用于记录每个前缀和出现的次数。

在遍历数组时，累计前缀和 total。每次检查 total - k 是否存在于 prefix_map 中：

如果存在，说明之前某个位置的前缀和为 total - k，那么从该位置到当前元素之间的子数组和就是 k；

将对应出现次数加到结果 count 中；

最后将当前前缀和 total 的次数记录到哈希表中，以备后续使用。

代码实现

python

from typing import List

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        total = 0                  # 当前的前缀和
        count = 0                  # 满足条件的子数组数量
        prefix_map = {0: 1}           # 哈希表：key=前缀和，value=出现次数
                                   # 初始设为{0:1}，表示前缀和为0时有1种情况（空子数组）

        for num in nums:
            total += num  # 累加当前元素，更新前缀和

            # 如果存在一个之前的前缀和为 total - k，说明中间那段子数组和为 k
            if total - k in prefix_map:
                count += prefix_map[total - k]  # 累加这种情况的次数

            # 更新当前前缀和的出现次数
            prefix_map[total] = prefix_map.get(total, 0) + 1

        return count  # 返回满足条件的子数组总数

javascript

const subarraySum = function(nums, k) {
    // 当前的前缀和
    let total = 0;
    // 满足条件的子数组数量
    let count = 0;
    // 哈希表：key=前缀和，value=出现次数
    // 初始设为{0:1}，表示前缀和为0时有1种情况（空子数组）
    let prefix_map = {0: 1};

    for (let num of nums) {
        // 累加当前元素，更新前缀和
        total += num;

        // 如果存在一个之前的前缀和为 total - k，说明中间那段子数组和为 k
        if (prefix_map[total - k]) {
            // 累加这种情况的次数
            count += prefix_map[total - k];
        }

        // 更新当前前缀和的出现次数
        prefix_map[total] = (prefix_map[total] || 0) + 1
    }

    // 返回满足条件的子数组总数
    return count;
};

复杂度分析

时间复杂度：O(n)

空间复杂度：O(n)

链接

560 国际版

560 中文版