subarraySum

560. 和为k的子数组

分析

定义前缀和：
- 用 sum 表示从数组起点到当前位置的元素总和
- 任意连续子数组的和可以通过前缀和的差来计算：sum[i] - sum[j] = k => sum[i] - k = sum[j]
使用哈希表存储前缀和出现的次数：
- 哈希表 hash 的键表示前缀和的值，值表示该前缀和出现的次数
- 初始状态下，将前缀和 0 的计数置为 1（代表从起点到当前位置的子数组和可能为 k ）
遍历数组，动态更新结果：
- 遍历数组中的每个元素，将当前值累加到 sum
- 检查 hash 中是否存在键 sum - k：
  - 若存在，说明从某个之前的位置到当前的位置的子数组和为 k ，将其对应的次数累加到结果 res 中
- 更新 hash，增加当前前缀和 sum 的计数
返回结果：
- 遍历结束后，结果 res 即为和为 k 的子数组个数

时间复杂度

遍历数组：O(n)，其中 n 是数组的长度
哈希表操作：平均时间复杂度为 O(1)

总时间复杂度：O(n)

空间复杂度

使用了哈希表存储前缀和及其次数，空间复杂度为 O(n)，其中 n 是数组的长度

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


class Solution
{
public:
    int subarraySum(vector<int>& nums, int k)
    {
        std::unordered_map<int, int> hash; // 存储前缀和及其出现次数
        int res = 0, sum = 0;

        hash[0] = 1; // 初始化前缀和 0 的计数为 1

        for (int num : nums)
        {
            sum += num;            // 更新前缀和
            res += hash[sum - k];  // 检查是否存在前缀和满足条件
            ++ hash[sum];           // 更新当前前缀和的计数
        }

        return res;
    }
};