1. 题目描述（题目链接）
给你一个整数数组 nums 和一个整数 k，请你统计并返回该数组中和为 k 的子数组的个数。
注意：
子数组是数组中元素的连续非空序列。
数组中可能包含负数。
数据范围：
示例：
输入：
nums = [1, 1, 1],k = 2
输出：2
解释：共有两个子数组的和为 2，分别是[1, 1](下标 0-1) 和[1, 1](下标 1-2)。
2. 解法一：暴力枚举
2.1 核心思想
最直观的思路是：枚举所有的子数组，并计算它们的和。
我们可以使用两层循环：
外层循环
i枚举子数组的左边界。内层循环
j枚举子数组的右边界。在内层循环中，维护一个变量
sum，累加从i到j的元素。如果sum == k，则计数器加一。
2.2 代码实现 (C++)
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
int ans = 0;
int n = nums.size();
// 枚举左边界 i
for (int i = 0; i < n; i++) {
int sum = 0; // 每次更换左边界，重置 sum
// 枚举右边界 j
for (int j = i; j < n; j++) {
sum += nums[j]; // 累加当前元素
if (sum == k) {
ans++;
}
// 注意：这里不能因为 sum > k 就 break，因为数组中存在负数
}
}
return ans;
}
};
2.3 复杂度分析
时间复杂度：O(N2)。有两层嵌套循环
空间复杂度：O(1)。只使用了常数级别的额外空间。
3. 解法二：前缀和 + 哈希表（最优解）
暴力解法的时间瓶颈在于：对于每个右边界 j，我们都重新计算了从 i 到 j 的和。我们可以利用前缀和来优化这个计算过程。
3.1 核心推导
定义 preSum[i] 为数组从第 0 个元素到第 i 个元素的总和。
那么，子数组 nums[i...j] 的和可以表示为：
Sum(i,j)=preSum[j]−preSum[i−1]
题目要求 Sum(i, j) == k，代入公式得：
preSum[j]−preSum[i−1]=k
移项得：
preSum[i−1]=preSum[j]−k
当我们遍历到位置 j 时，我们只需要知道在 j 之前，有多少个前缀和等于 preSum[j] - k 即可。
3.2 哈希表的作用
为了快速查询“之前出现过多少次某个前缀和”，我们可以使用哈希表 (unordered_map)。
Key：前缀和的值。
Value：该前缀和出现的次数。
3.3 细节处理
初始化
map[0] = 1：这是为了处理从数组起始位置 (索引 0) 开始的子数组。如果preSum[j]本身就等于k，那么preSum[j] - k = 0，此时我们需要哈希表里存在0这个前缀和，且次数为 1。边遍历边更新：先计算当前
preSum，去哈希表里查找preSum - k的次数累加到ans，然后再把当前的preSum放入哈希表。顺序不能颠倒，否则会把自己也算进去，导致错误。
3.4 代码实现 (C++)
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
unordered_map<int, int> mp;
// 初始化，前缀和为0的情况出现了1次
mp[0] = 1;
int preSum = 0; // 记录当前前缀和
int ans = 0; // 记录结果
for (int i = 0; i < nums.size(); i++) {
preSum += nums[i]; // 计算到当前位置的前缀和
// 核心逻辑：如果 (当前前缀和 - k) 在哈希表中存在
if (mp.find(preSum - k) != mp.end()) {
ans += mp[preSum - k];
}
// 将当前前缀和存入哈希表
mp[preSum]++;
}
return ans;
}
};
3.5 复杂度分析
时间复杂度：O(N)。只需要遍历一次数组，哈希表的插入和查找操作平均时间复杂度为 O(1)。
空间复杂度：O(N)。最坏情况下，数组中的每个元素都会产生不同的前缀和，哈希表需要存储 N 个键值对。
转载自 CSDN-专业IT技术社区
原文链接：https://blog.csdn.net/longlongzihan/article/details/167178757
