[!info] related notes

• 前置知识: 前缀和
• 相关题目: 两数之和, [[continuous-subarray-sum|连续子数组和]]

和为k的子数组

目标

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

示例：

输入: nums = [1,1,1], k = 2
输出: 2
解释: [1,1] 出现两次（索引 0-1 和 1-2）

输入: nums = [1,2,3], k = 3
输出: 2
解释: [1,2] 和 [3] 各一次

前置知识

前缀和

前缀和 prefix[i] 表示从索引 0 到 i-1 的元素之和：

nums:       [1,  2,  3,  4]
prefix:   [0, 1,  3,  6, 10]
            ^   ^       ^
         空数组  到idx=0  到idx=2

子数组 nums[i..j] 的和 = prefix[j+1] - prefix[i]

问题转化

要找 nums[i..j] 的和等于 k，即：

prefix[j+1] - prefix[i] = k
→ prefix[i] = prefix[j+1] - k

遍历时，对于当前前缀和 curr，需要查找之前出现过多少次 curr - k。

解题步骤

算法思路

1. 使用哈希表记录每个前缀和出现的次数
2. 从左往右遍历数组，维护当前前缀和 curr
3. 每步检查 curr - k 在哈希表中出现的次数，累加到结果
4. 将当前前缀和加入哈希表

代码实现 - JavaScript

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var subarraySum = function(nums, k) {
    // 前缀和 -> 出现次数
    const prefixMap = new Map()
    prefixMap.set(0, 1)  // 空前缀和为 0，出现 1 次

    let count = 0
    let curr = 0

    for (const num of nums) {
        curr += num

        // 查找是否存在前缀和等于 curr - k
        if (prefixMap.has(curr - k)) {
            count += prefixMap.get(curr - k)
        }

        // 记录当前前缀和
        prefixMap.set(curr, (prefixMap.get(curr) || 0) + 1)
    }

    return count
}

代码实现 - Python

def subarraySum(nums: list[int], k: int) -> int:
    from collections import defaultdict

    prefix_map = defaultdict(int)
    prefix_map[0] = 1  # 空前缀和为 0

    count = 0
    curr = 0

    for num in nums:
        curr += num

        # 查找是否存在前缀和等于 curr - k
        if curr - k in prefix_map:
            count += prefix_map[curr - k]

        # 记录当前前缀和
        prefix_map[curr] += 1

    return count

执行过程示例

以 nums = [1, 2, 3], k = 3 为例：

步骤	num	curr	curr - k	查找结果	count	prefixMap
初始	-	0	-	-	0	{0: 1}
1	1	1	-2	未找到	0	{0: 1, 1: 1}
2	2	3	0	找到 1 次	1	{0: 1, 1: 1, 3: 1}
3	3	6	3	找到 1 次	2	{0: 1, 1: 1, 3: 1, 6: 1}

最终返回 count = 2。

复杂度分析

维度	复杂度	说明
时间	O(n)	单次遍历，哈希表操作 O(1)
空间	O(n)	哈希表最多存储 n 个不同的前缀和

对比暴力解法 O(n^2)，有显著提升。

变体问题

1. 和为 k 的最长子数组

将哈希表存储改为记录每个前缀和首次出现的位置：

var maxSubArrayLen = function(nums, k) {
    const firstPos = new Map()
    firstPos.set(0, -1)

    let maxLen = 0
    let curr = 0

    for (let i = 0; i < nums.length; i++) {
        curr += nums[i]
        if (firstPos.has(curr - k)) {
            maxLen = Math.max(maxLen, i - firstPos.get(curr - k))
        }
        if (!firstPos.has(curr)) {
            firstPos.set(curr, i)
        }
    }

    return maxLen
}

2. 元素只能为正整数时（双指针/滑动窗口）

当数组元素全为正整数时，可以使用滑动窗口实现 O(1) 空间：

var subarraySum = function(nums, k) {
    let count = 0, left = 0, sum = 0

    for (let right = 0; right < nums.length; right++) {
        sum += nums[right]
        while (sum > k) {
            sum -= nums[left++]
        }
        if (sum === k) count++
    }

    return count
}

[!warning] 注意 滑动窗口仅适用于元素全为正整数的场景。本题元素可为负数，必须使用前缀和+哈希表。

3. 和不超过 k 的子数组数量

将条件从 == k 改为 <= k，需要结合有序数据结构（如平衡树/BIT）。

Related notes

• 前缀和
• 两数之和
• 滑动窗口