前缀和专题实战
在子数组统计类问题中，暴力枚举往往会导致 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，则 。
但在 C++ 中，负数取模的结果可能为负（例如 ），而数学上的同余要求余数非负。因此需要统一处理公式：。
