前缀和专题实战
在算法面试中，涉及子数组求和的问题往往可以通过前缀和 + 哈希表的组合来优化。今天重点讲解两道经典题目：LeetCode 560（和为 K 的子数组）与 974（和可被 K 整除的子数组）。
1. 和为 K 的子数组
核心思路：
假设 sum[i] 表示从索引 0 到 i 的前缀和。如果我们想找到以 i 结尾、和为 k 的子数组，实际上是在寻找是否存在某个起始位置 x，使得 sum[i] - sum[x-1] == k。
移项后得到：sum[x-1] == sum[i] - k。
这意味着，我们不需要维护整个前缀和数组，只需要用一个哈希表记录遍历过程中每个前缀和出现的次数。当计算到当前位置的当前前缀和 currentSum 时，直接查询哈希表中 currentSum - k 出现过的次数即可。
注意点：
初始化时，哈希表中需放入 {0: 1}。这代表前缀和为 0 的情况出现过一次（即空数组），用于处理从数组开头开始就满足条件的情况。
代码实现：
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
unordered_map<int, int> hash;
hash[0] = 1; // 初始状态，前缀和为 0 出现 1 次
int n = nums.size();
int sum = 0, ret = 0;
for (auto x : nums) {
sum += x;
if (hash.count(sum - k)) {
ret += hash[sum - k];
}
hash[sum]++;
}
return ret;
}
};
时间复杂度 O(n)，空间复杂度 O(n)。
2. 和可被 K 整除的子数组
这道题是上一题的变种，核心在于利用同余定理处理整除条件。
前置知识：
如果 (a - b) % n == 0，则 a % n == b % n。也就是说，两个数相减能被 n 整除，等价于它们对 n 取模的结果相同。