和能被 K 整除的子数组有多少个？前缀和取模怎么用？

简化版

统计和能被 K 整除的连续子数组个数。关键:子数组 [l..r] 的和能被 K 整除 ⟺ prefix[r+1] 和 prefix[l] 对 K 的余数相同(同余)。所以用哈希表记录每个「前缀和余数」出现的次数,遍历时对当前余数 r,累加「之前出现过多少个相同余数」。注意负数取模要规整到非负:((sum % k) + k) % k。O(n)。

详细版

int subarraysDivByK(int[] nums, int k) {
    Map<Integer, Integer> count = new HashMap<>();
    count.put(0, 1);                         // 余数 0 出现 1 次（空前缀）
    int sum = 0, res = 0;
    for (int x : nums) {
        sum += x;
        int r = ((sum % k) + k) % k;         // 规整到 [0, k) 的非负余数
        res += count.getOrDefault(r, 0);     // 之前有多少个相同余数
        count.merge(r, 1, Integer::sum);
    }
    return res;
}

同余判断:两个前缀和余数相同 → 它们之间的子数组和是 K 的倍数。
负数取模:sum % k 在负数时可能是负的(Java 里 -1 % 3 == -1),用 ((sum%k)+k)%k 规整到 [0, k)。
count.put(0, 1):处理「前缀本身就能被 K 整除」的情况。

完整版教学

一、核心:同余等价于「差是 K 的倍数」

这题是「和为 K 的子数组」的变体,核心从「差为 K」变成「差是 K 的倍数」。数学基础是同余:

子数组 [l..r] 和能被 K 整除
⟺ (prefix[r+1] - prefix[l]) % K == 0
⟺ prefix[r+1] ≡ prefix[l]  (mod K)   ← 两者对 K 同余（余数相同）

所以问题变成:有多少对前缀和,它们对 K 的余数相同。每一对相同余数,就对应一个「和能被 K 整除」的子数组。这个「差为倍数 ⟺ 同余」的转化是本题的灵魂。

二、哈希记录「余数 → 出现次数」

既然只关心余数是否相同,就用哈希表记录每个余数出现了多少次(而不是记前缀和本身)。遍历时:

算出当前前缀和的余数 r。
之前出现过多少个余数也是 r 的前缀和,就有多少个以当前位置结尾、和能被 K 整除的子数组,累加。
把当前余数 r 存入(次数 +1)。

和「和为 K」一样是「先查后存」+ count[0]=1 初始化,只是把「前缀和」换成了「前缀和余数」。

三、负数取模的坑(重点)

这是本题最容易错、也最常被追问的点。在很多语言(Java、C++)里,负数取模的结果可能是负的:-1 % 3 在 Java 里是 -1,不是 2。但我们要的余数应该在 [0, k) 内。如果不规整,-1 和 2 会被当成不同余数,同余判断就错了。规整方法:

int r = ((sum % k) + k) % k;   // 先 %k，可能为负，+k 变正，再 %k 收进 [0,k)

先 % k 得到 (-k, k) 的值,+ k 变成 (0, 2k),再 % k 收进 [0, k)。处理带负数的取模题,一定要这样规整余数,否则结果错。

四、组合数视角(为什么累加出现次数)

如果某个余数 r 在遍历过程中总共出现了 c 次,那么这 c 个前缀和两两配对,能组成 C(c, 2) = c(c-1)/2 个「和能被 K 整除的子数组」。上面的代码用「边遍历边累加 count[r]」的方式,等价于逐步累加这个组合数——每遇到一个新的相同余数,就和之前所有相同余数配对。两种理解(边遍历累加 / 最后算组合数)结果一致。

五、走一个例子

nums = [4,5,0,-2,-3,1], k = 5
前缀和: 4, 9, 9, 7, 4, 5
余数:   4, 4, 4, 2, 4, 0
count[0]=1 起步：
  r=4: count[4]=0→res+0, 存 count[4]=1
  r=4: res+1(前面一个4), count[4]=2
  r=4: res+2, count[4]=3
  r=2: res+0, count[2]=1
  r=4: res+3, count[4]=4
  r=0: res+1(初始的0), count[0]=2
res = 0+1+2+0+3+1 = 7 ✓

六、复杂度与同类题

时间 O(n)、空间 O(k)(余数只有 k 种)。
同类(都是「前缀量 + 哈希」):
- 和为 K 的子数组:记前缀和,查 sum - k。
- 和能被 K 整除:记前缀和余数,查相同余数。
- 连续数组(0/1 等量):0 当 -1,查相同前缀和(记首次下标求最长)。

框架一致,只是「记什么量、查什么」不同。

七、从公式证明到手算闭环

这道题成立的核心是：两个前缀和具有相同规范化余数，当且仅当它们的差能被 K 整除。先明确每个数组槽或哈希键的数学含义，代码中的下标偏移才不是死记硬背。

r = ((sum % K) + K) % K
answer += count[r]
count[r]++
count[0] = 1

带数字推演：[4,5,0,-2,-3,1]、K=5 的前缀余数规范化后重复出现；每次余数 r 已出现 c 次就新增 c 个区间。手算时同时列出原数组、辅助状态和本轮新增答案，能够直接发现端点偏一、初始化遗漏以及更新顺序错误。

核对维度	本题结论
正确性依据	两个前缀和具有相同规范化余数，当且仅当它们的差能被 K 整除
复杂度	时间 O(n)，空间最多 O(min(n,K))；K 较小时可用长度 K 的数组
关键边界	K 通常要求正数；Java/C++ 的负数 `%` 可能为负，必须规范化；答案最多 n(n+1)/2，宜用 long

记忆钩子：不要先背代码，先说清辅助状态“代表哪一段”；公式只是把重叠部分消掉或把边界影响传播出去。

八、实现边界与测试策略

实现时最需要警惕的是：K 通常要求正数；Java/C++ 的负数 % 可能为负，必须规范化；答案最多 n(n+1)/2，宜用 long。这不是语法细节，而是决定算法是否仍满足题目语义的前提。

提交前应分别验证：

空数组或最小合法规模，确认哨兵位置和初始化。
查询或更新紧贴左、上边界，确认没有访问负下标。
查询或更新紧贴右、下边界，确认“终点后一位”不会越界。
包含 0、负数或重复前缀的样例，确认频次与取模语义。
大数输入，确认累计和、乘积或答案数量的整数类型足够。

如果需求从离线变成在线，或从单次恢复变成更新查询交错，原方法可能不再合适。此时应根据操作类型改用树状数组、线段树、二维结构或其他能维护动态状态的数据结构，而不是强行沿用静态前缀模型。

九、常见误区与追问

误区：只要当前前缀余数为 0 才有答案。 任意两个相同余数前缀之差都可整除。
误区：负余数可直接作为哈希键且不影响。 等价余数可能被分成 -2 与 3 两组，导致漏计。
误区：每个余数只保留一次即可。 求数量要累加此前全部同余前缀。
追问：为什么累加 count[r]？ 当前前缀与每个旧同余前缀都形成不同区间。
追问：空间一定是 O(n)？ 余数只有 K 种，数组实现上界是 O(K)。
追问：K=0 怎么办？ 整除 0 无定义；若题目允许需另行定义为子数组和等于 0。

十、加强记忆

和能被 K 整除的子数组:子数组和是 K 的倍数 ⟺ 两端前缀和对 K 同余。哈希记录每个余数的出现次数,遍历累加 count[余数](先查后存、count[0]=1)。负数取模必须规整:((sum%k)+k)%k 收进 [0,k),否则同余判断错。O(n)、空间 O(k)。和「和为 K 子数组」是同一框架,区别是「记余数、查相同余数」而非「记前缀和、查差为 K」。

简化版

详细版