整除子数组：把同余前缀分组
问题与默认样例
Section titled “问题与默认样例”数组 [4,5,0,−2,−3,1]，K=5。统计区间和能被正整数 K 整除的非空连续子数组数量。负倍数和 0 都能整除，K 不能是 0。
合法闭区间为 [0,5]、[1,1]、[1,2]、[1,4]、[2,2]、[2,4]、[3,4]，共 7。其中 [3,4] 的和为 −5，[2,2] 的和为 0，不能只寻找正数和。
从区间差到同余分组
Section titled “从区间差到同余分组”区间 [l,r] 的和是 P[r+1]−P[l]。设两个前缀分别是 aK+m、bK+m，差就是 (a−b)K，必然可整除。因此无需找完全相等的前缀，只要找相同规范化余数的历史前缀。
默认例子前缀为 [0,4,9,9,7,4,5]，规范化余数为 [0,4,4,4,2,4,0]。例如当前前缀 9 与历史前缀 4 的余数都是 4，差为 5，就找到一个区间。
表中的键从“完整前缀值”改成“余数”，值仍是历史出现次数。先放入空前缀余数 freq[0]=1；查完贡献后再记录当前余数，保证非空区间。
为什么 Java 需要归一化
Section titled “为什么 Java 需要归一化”Java 中 -1 % 5 == -1，但数学上的同余类还包括余数 4。前缀 −1 与前缀 4 的差是 5，应该能配对。
采用 ((cur % K)+K)%K，将余数统一到 0…K−1。cur 用 long，运算完成后再转为 int。不要简单取绝对值：−1 应进余数 4 的桶，而不是余数 1。
手动推演：让同余历史贡献答案
Section titled “手动推演：让同余历史贡献答案”优化版每轮累计前缀、计算余数、查询频次、累加贡献、记录余数；暴力版检查每个候选区间的和是否能整除。都支持负数与零。
演示尚未初始化；如果此提示持续显示，脚本未能加载。文字与 Java 示例仍可阅读。
查看 Java 代码 · 当前动作语句高亮
高亮表示刚执行完成的语句，一步可以覆盖多行；最后一步也包含返回值。代码仅为正确解法，错误实验独立展示。
前缀解法
import java.util.HashMap;import java.util.Map;class Solution { public long countDivisibleByK(int[] nums, int k) { Map<Integer, Integer> freq = new HashMap<>(); freq.put(0, 1); long cur = 0L, ans = 0L; for (int x : nums) { cur += x; int mod = (int) ((cur % k + k) % k); int hit = freq.getOrDefault(mod, 0); ans += hit; freq.put(mod, freq.getOrDefault(mod, 0) + 1); } return ans; }}暴力解法
class Solution { public long countDivisibleByK(int[] nums, int k) { long ans = 0L; for (int left = 0; left < nums.length; left++) { long sum = 0L; for (int right = left; right < nums.length; right++) { sum += nums[right]; if (sum % k == 0) ans++; } } return ans; }}cur 与 ans 都用 long，避免前缀总和或子数组数量超出 int。增强 for 中没有数组下标变量，图中的 i 是教学定位信息。
此模板要求 k > 0。cur 是 long，因此规范化中的加法先在 long 范围计算，再安全转为 int。
本页是与 Java 示例对应的教学推演，不运行任意 Java。加载完成后可断网操作；刷新清空输入、步骤和自测答案。
默认样例逐轮核对
| 原数组 i | cur | 余数 | 历史命中 | 累计数量 |
|---|---|---|---|---|
| 0 | 4 | 4 | 0 | 0 |
| 1 | 9 | 4 | 1 | 1 |
| 2 | 9 | 4 | 2 | 3 |
| 3 | 7 | 2 | 0 | 3 |
| 4 | 4 | 4 | 3 | 6 |
| 5 | 5 | 0 | 1 | 7 |
为什么不漏不重，工作量如何变化
Section titled “为什么不漏不重，工作量如何变化”每个合法区间在处理其唯一右端点时，恰好与一个更早的同余前缀配对。每个历史位置记一次，所以相同余数有几次，就新增几段。
长度 n 的数组，暴力检查 n(n+1)/2 个候选，时间 O(n²)。优化扫描做 n 次匹配查询与 n 次频次记录，平均时间 O(n)；HashMap 最多保存 min(n+1,K) 个不同余数，额外空间 O(min(n+1,K))。如果改用长度 K 的频次数组，还需承担 O(K) 分配与初始化成本。
K=1 时所有区间都可整除，答案应为 n(n+1)/2。全零数组也一样。这是很好的边界核对方式。
错误实验：数学上同余，程序却分开了
Section titled “错误实验：数学上同余，程序却分开了”独立样例 [−1,5]，K=5。前缀是 0、−1、4。正确做法把后两个前缀都放在余数 4 的桶，找到区间 [1,1]，结果 1。
故意不归一化时，−1 和 4 进入两个桶，错误结果 0。原数组中的负数仍合法，错误出在分组方式。
演示尚未初始化；如果此提示持续显示，脚本未能加载。文字与 Java 示例仍可阅读。
Java：只改键的含义，不改计数语义
Section titled “Java：只改键的含义，不改计数语义”查看联动 Java。与上一课相比，不再查询 cur−K，而是计算并查询当前余数 mod，最后记录同一个 mod。HashMap 的键可以用 Integer，累计前缀 cur 与答案 ans 仍保留 long。
暴力代码用 sum%K==0 判整除时无需把余数改成非负，因为只判断是否为 0；归一化针对的是优化方法中需要比较余数是否属于同一组。
自测：说明负数是怎样归组的
Section titled “自测：说明负数是怎样归组的”来源与继续学习
Section titled “来源与继续学习”依据 S2 技巧 3 的 [4,5,0,−2,−3,1] 样例、S1 同余模型与负数压力测试、S3 §5 的取模边界整理。错误实验与自测为新增设计。返回专题，选择进阶方向 →