前缀和算法实战：和为 K 与整除 K 的子数组问题

关键点：

• 哈希表初始存入 {0: 1}，是为了处理前缀和本身即为 k 的情况（即子数组从第一个元素开始）。
• 遍历时先查询再更新，避免将当前元素计入自身。

和可被 K 整除的子数组

题目链接：

974. 和可被 K 整除的子数组 - 力扣（LeetCode）

题目描述：

前置知识：同余定理

若 (a - b) % n == 0，则 a % n == b % n。即两个数相减能被 n 整除，等价于它们对 n 取模的结果相同。

注意负数取模：

C++ 中负数取模结果可能为负（如 -1 % 3 = -1）。为保证余数非负，统一使用公式：(a % n + n) % n。

解题思路：

逻辑与前题类似，但判断条件变为余数相等。

设 sum[i] 为当前前缀和，sum[x-1] 为之前某位置的前缀和。若子数组 [x, i] 的和能被 k 整除，则：

(sum[i] - sum[x-1]) % k == 0
=> sum[i] % k == sum[x-1] % k

因此，只需统计之前出现过的、与当前前缀和同余的个数。

C++ 实现：

class Solution {
public:
    int subarraysDivByK(vector<int>& nums, int k) {
        unordered_map<int, int> hash;
        hash[0 % k] = 1; // 初始化，处理前缀和本身能被 k 整除的情况
        int sum = 0, ret = 0;
        for (auto x : nums) {
            sum += x;
            int r = (sum % k + k) % k; // 修正负数取模
            if (hash.count(r)) {
                ret += hash[r];
            }
            hash[r]++;
        }
        return ret;
    }
};

总结：

这两道题展示了前缀和与哈希表的经典组合。第一题关注差值，第二题关注余数。实际编码时务必注意边界条件，特别是负数取模的处理，这是容易踩坑的地方。