算法实战：和为 K 的子数组与和可被 K 整除的子数组

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。