和为 K 的子数组 - Stellar Observer Protocol

636 字

3 分钟

和为 K 的子数组

2025-08-29

Algorithms

数组

/

哈希表

/

前缀和

题目描述#

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

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

解题思路#

前缀和转换：
- 将子数组和问题转化为前缀和之差问题
哈希表优化：
- 使用哈希表记录各前缀和出现次数
实时计算：
- 遍历时计算当前前缀和 curr_sum
差值匹配：
- 查找 curr_sum - k 是否在历史前缀和中
计数更新：
- 匹配成功则累加对应出现次数
更新存储：
- 将当前前缀和加入哈希表

关键洞察#

前缀和性质：
- sum[i..j] = prefix[j] - prefix[i-1]
两数差转化：
- prefix[j] - prefix[i] = k 等价于 prefix[i] = prefix[j] - k
哈希表高效查询：
- O(1) 时间查询历史前缀和
初始化技巧：
- 预先存入 {0:1} 处理从头开始的子数组
顺序处理：
- 单次遍历完成计数，避免嵌套循环
负数和处理：
- 天然支持含负数的数组

复杂度分析#

指标	说明
时间复杂度	O(n)：单次遍历数组
空间复杂度	O(n)：哈希表存储前缀和
最优情况	O(n)：所有元素相同时
最坏情况	O(n)：前缀和均不同时

代码实现#

1
/**
2
 * @param {number[]} nums
3
 * @param {number} k
4
 * @return {number}
5
 */
6
var subarraySum = function (nums, k) {
7
    let result = 0, sum = 0;
8
    const map = { 0: 1 };
9
    for (const num of nums) {
10
        sum += num;
11
        if (map[sum - k]) {
12
            result += map[sum - k];
13
        }
14
        map[sum] = (map[sum] || 0) + 1
15
    }
16
    return result;
17
};

1
use std::collections::HashMap;
2

3
impl Solution {
4
    pub fn subarray_sum(nums: Vec<i32>, k: i32) -> i32 {
5
        let mut sum = 0;
6
        let mut result = 0;
7
        let mut map = HashMap::new();
8
        map.insert(0, 1);
9
        for num in nums {
10
            sum = sum+num;
11
            if let Some(&count) = map.get(&(sum-k)) {
12
                result+=count;
13
            }
14
            *map.entry(sum).or_insert(0)+=1;
15
        }
16
        return result;
17
    }

1
from collections import defaultdict
2

3
class Solution:
4
    def subarraySum(self, nums: List[int], k: int) -> int:
5
        map = defaultdict(int)
6
        map[0] = 1
7
        count = 0
8
        sum = 0
9

10
        for num in nums:
11
            sum+=num
12
            if sum - k in map:
13
                count += map[sum-k]
14
            map[sum]+=1
15

16
        return count