前缀和算法实战
在处理连续子数组求和问题时，前缀和（Prefix Sum）配合哈希表往往能将时间复杂度从 O(n²) 优化到 O(n)。下面通过两道经典题目，深入剖析这一技巧的核心逻辑。
560. 和为 K 的子数组
题目描述： 给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续子数组的个数。
解题思路：
假设 sum[i] 表示从下标 0 到 i 的前缀和。如果存在某个起始位置 x，使得区间 [x, i] 的和等于 k，那么必然满足：
sum[i] - sum[x-1] = k
即：
sum[x-1] = sum[i] - k
这意味着，当我们遍历到当前位置 i 时，只需要统计在 i 之前有多少个前缀和等于 sum[i] - k。为了高效查询，我们使用哈希表记录每个前缀和出现的次数。
注意初始化 hash[0] = 1，这代表前缀和为 0 的情况出现了一次（即空数组），用于处理从索引 0 开始就满足条件的情况。
代码实现：
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
unordered_map<int, int> hash;
hash[0] = 1; // 初始化，处理从开头开始的子数组
int sum = 0, ret = 0;
for (auto x : nums) {
sum += x;
if (hash.count(sum - k)) {
ret += hash[sum - k];
}
hash[sum]++;
}
return ret;
}
};
974. 和可被 K 整除的子数组
题目描述： 给定一个整数数组 A，返回其中元素之和可被 K 整除的非空连续子数组的数目。
前置知识补充：
这道题的关键在于同余定理。如果 (a - b) % n == 0，则 a % n == b % n。
换句话说，如果两个前缀和相减能被 K 整除，那么这两个前缀和对 K 取模的结果一定相同。
负数取模的处理：
C++ 中的 % 运算符对负数的处理可能产生负结果（例如 -1 % 3 = -1）。为了保证余数非负，统一使用公式：(a % n + n) % n。
解题思路：
设当前前缀和为 sum，我们需要寻找之前的前缀和 prev_sum，使得 (sum - prev_sum) % K == 0。
根据同余定理，这等价于 。
因此，我们维护一个哈希表，记录每个余数出现的次数。遇到相同的余数时，累加对应的计数即可。
