前缀和专题实战
29. 和为 K 的子数组
题目链接： 560. 和为 K 的子数组 - LeetCode
题目描述
给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。
示例
输入：nums = [1,1,1], k = 2 输出：2 解释：[1,1] 在索引 0-1 和 1-2 处各出现一次。
解题思路
这道题的核心在于利用前缀和配合哈希表来优化查找效率。
想象一下，如果我们定义 sum[i] 为从下标 0 到 i 的所有元素之和。那么，任意区间 [x, i] 的和就可以表示为 sum[i] - sum[x-1]。
我们的目标是找到有多少个起始位置 x，使得 sum[i] - sum[x-1] == k。移项后得到：
sum[x-1] == sum[i] - k
这意味着，当我们遍历到当前位置 i 时，只需要知道在 i 之前有多少个前缀和等于 当前前缀和 - k，就能确定以 i 结尾的满足条件的子数组数量。
为了高效查询，我们不需要维护一个完整的前缀和数组，而是用一个哈希表（unordered_map）记录每个前缀和出现的次数。一边计算当前前缀和，一边更新哈希表。
注意初始化 hash[0] = 1，这代表前缀和为 0 的情况出现了 1 次（即空数组），用于处理从数组开头就满足条件的情况。
代码实现
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;
}
};
30. 和可被 K 整除的子数组
题目链接： 974. 和可被 K 整除的子数组 - LeetCode
题目描述
给定一个整数数组 A，返回其中元素之和可被 K 整除的非空连续子数组的数目。
前置知识补充
同余定理
如果 (a - b) % n == 0，则 a % n == b % n。
换句话说，如果两个数相减能被 n 整除，那么它们对 n 取模的结果相同。
例如：(26 - 2) % 12 == 0，则 26 % 12 == 2 % 12 == 2。
负数取模问题
C++ 中负数取模的结果可能为负。例如 -1 % 3 = -1。
为了确保结果始终为正，统一使用公式：(a % n + n) % n。
例如：(-1 % 3 + 3) % 3 = 2。
解题思路
这道题的思路与上一题类似，但需要处理整除条件。
设 sum[i] 为 [0, i] 区间的前缀和。若子数组 [x, i] 的和能被 K 整除，则：
(sum[i] - sum[x-1]) % K == 0
根据同余定理，这等价于：
sum[i] % K == sum[x-1] % K
也就是说，只要两个前缀和对 K 取模的余数相同，它们之间的子数组和就能被 K 整除。
我们需要统计在当前位置 i 之前，有多少个前缀和的余数与 sum[i] % K 相同。同样使用哈希表存储余数出现的次数。关键点是处理负数余数，确保存入哈希表的键都是非负的。
代码实现
class Solution {
public:
int subarraysDivByK(vector<int>& nums, int k) {
unordered_map<int, int> hash;
hash[0] = 1; // 余数为 0 的初始计数
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;
}
};
总结
这两道题展示了前缀和技巧在子数组统计问题中的强大应用。通过引入哈希表，我们将时间复杂度从 O(n²) 优化到了 O(n)。特别是第二题，巧妙结合同余定理和负数取模处理，解决了看似复杂的整除判定问题。在实际编码中，注意边界条件（如初始值设置）和语言特有的取模行为，能避免很多潜在 Bug。
