前缀和技巧实战：和为 K 的子数组与和可被 K 整除的子数组

974. 和可被 K 整除的子数组

题目链接： LeetCode 974

题目描述： 给定一个整数数组 A，返回其中「元素之和可被 K 整除」的非空连续子数组的数目。

解题思路： 这道题是上一题的变体，核心在于判断子数组和是否能被 K 整除。根据同余定理，如果 (b - a) % K == 0，则 b % K == a % K。也就是说，如果两个前缀和对 K 取模的结果相同，那么它们之间的差值（即中间那段子数组的和）一定能被 K 整除。

因此，我们需要统计的是前缀和模 K 的余数。这里有一个关键点：负数取模。在 C++ 中，负数取模可能得到负数结果（例如 -1 % 3 = -1）。为了保证余数非负且符合数学定义，统一使用公式 (sum % K + K) % K 来处理。

同样地，使用哈希表记录每个余数出现的次数。当计算当前前缀和的余数 r 时，若哈希表中已存在 r，则说明之前有若干次前缀和与当前前缀和同余，累加对应的次数。

前置知识补充：

• 同余定理： 若 (a - b) % n == 0，则 a % n == b % n。
• 负数取模处理： 使用 (a % n + n) % n 确保结果始终为正。

参考实现：

class Solution {
public:
    int subarraysDivByK(vector<int>& nums, int k) {
        unordered_map<int, int> hash;
        hash[0] = 1; // 初始前缀和为 0，余数为 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。掌握这一模式，能高效解决大量涉及区间和统计的问题。