前缀和专题实战
在子数组统计类问题中，暴力枚举往往会导致 O(n^2) 的时间复杂度。引入前缀和（Prefix Sum）配合哈希表，可以将查询效率优化至 O(1)，从而将整体复杂度降为 O(n)。这里我们结合两道经典题目，深入探讨这一技巧的应用细节。
1. 和为 K 的子数组
题目核心： 给定一个整数数组和一个整数 k，找到该数组中和为 k 的连续子数组的个数。
思路解析：
假设当前遍历到位置 i，前缀和为 sum[i]。如果存在某个起始位置 x，使得区间 [x, i] 的和为 k，那么必然满足：
sum[i] - sum[x-1] = k
即：
sum[x-1] = sum[i] - k
这意味着，我们只需要在遍历过程中，记录之前出现过的每一个前缀和及其次数。当计算到当前位置的前缀和时，直接去哈希表中查找 sum[i] - k 出现的次数即可累加结果。
代码实现：
注意初始化 hash[0] = 1，这代表前缀和为 0 的情况（即从数组开头开始的子数组）。
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
unordered_map<int, int> hash;
// 初始化：前缀和为 0 的情况出现一次
hash[0] = 1;
int n = nums.size();
int sum = 0, ret = 0;
for (auto x : nums) {
sum += x;
// 如果之前出现过 sum - k，说明存在以当前位置结尾、和为 k 的子数组
if (hash.count(sum - k)) {
ret += hash[sum - k];
}
// 更新当前前缀和的出现次数
hash[sum]++;
}
return ret;
}
};
2. 和可被 K 整除的子数组
题目核心： 给定一个整数数组和一个整数 k，返回该数组中和可被 k 整除的非空连续子数组的数目。
前置知识：
这道题是上一题的变体，关键在于处理负数取模。
根据同余定理，若 (a - b) % k == 0，则 a % k == b % k。
但在 C++ 中，负数取模的结果可能为负（例如 -1 % 3 = -1），而数学上的同余要求余数非负。因此需要统一处理公式：(a % k + k) % k。
思路解析：
逻辑与前题类似，只是判断条件变为余数相等。
设当前前缀和为 sum，我们需要找之前有多少个前缀和 prev_sum 满足 (sum - prev_sum) % k == 0。
这等价于 sum % k == prev_sum % k。
为了兼容负数，我们在存入哈希表和查询时都使用 (sum % k + k) % k 作为键。
代码实现：
注意 hash[0%k] = 1 的初始化，以及取模时的正数化处理。
class Solution {
public:
int subarraysDivByK(vector<int>& nums, int k) {
unordered_map<int, int> hash;
// 初始前缀和为 0，其模 k 余数为 0
hash[0] = 1;
int sum = 0, ret = 0;
for (auto x : nums) {
sum += x;
// 关键：处理负数取模，确保余数在 [0, k-1] 范围内
int r = (sum % k + k) % k;
if (hash.count(r)) {
ret += hash[r];
}
hash[r]++;
}
return ret;
}
};
总结
这两道题展示了前缀和与哈希表的经典组合。第一题关注差值匹配，第二题关注同余关系。特别是第二题中，务必注意编程语言对负数取模的处理差异，通过 (val % k + k) % k 这种写法可以安全地保证余数始终为正，避免边界错误。时间复杂度均为 O(n)，空间复杂度为 O(min(n, k))。
