和可被 K 整除的子数组
子数组和可被 K 整除个数。
子数组和可被 K 整除个数。
当前前缀值是什么，需要查询哪一个过去前缀？
prefix mod K;map 存 mod 频次,同 mod 差为 K 倍数。
先说结论：这道题到底解决什么
怎样从“子数组和可被 K 整除个数。”推导出 前缀和 · 整除 K，并证明每次状态变化都不会漏掉答案？
中心结论：prefix mod K;map 存 mod 频次,同 mod 差为 K 倍数。
- 1.暴力方案在哪里重复计算，为什么仍然是正确基线？
- 2.当前前缀值是什么，需要查询哪一个过去前缀？
- 3.不变量“(prefix[j]-prefix[i])%K==0 ⇔ 两前缀 mod K 相同。”为什么能保证算法安全前进？
完整题目与题意拆解
子数组和可被 K 整除个数。
在本站主例中，子数组和可被 K 整除个数。
算法最终需要得到或观察：同 mod 前缀差构成 K 倍数子数组个数。
- • 输入：子数组和可被 K 整除个数。
- • 机器需要维护：prefix mod、map。
- • 最终可观察结果：同 mod 前缀差构成 K 倍数子数组个数。
先看清算法到底要维护什么
先建立输入、目标、输出和第一批状态，不急着进入模板。
子数组和 = prefix[r]-prefix[l-1],查 prefix-k 出现次数
第一层方案：暴力做法
每次重新计算区间会重复累加；前缀状态把区间信息变成两个历史状态的差或关系。
暴力方案的价值是确认题意并提供正确性基线。它通常会覆盖所有候选， 但没有保存已经确认的信息，因此同一状态会被重新计算。
重复工作究竟发生在哪里
把重复读取或重复搜索的区域明确标出，再决定优化必须保存什么。
子数组和 = prefix[r]-prefix[l-1],查 prefix-k 出现次数
整体地图：先做什么，再做什么
- 1建模把输入翻译成“前缀累计仪”，明确答案需要观察什么。
- 2状态只维护 prefix mod、map。
- 3转移每一步按照 prefix mod K;map 存 mod 频次,同 mod 差为 K 倍数。
- 4收尾读取 同 mod 前缀差构成 K 倍数子数组个数。，并复核边界与复杂度。
前缀累计仪：核心概念
把“某段区间”改写成“两个前缀之间的关系”。
这道题不是为了记住一个组件名称，而是为了让状态具有可解释的语义：prefix mod、map。
- • (prefix[j]-prefix[i])%K==0 ⇔ 两前缀 mod K 相同。
建立“前缀累计仪”心智模型
用主例建立核心状态，先预测下一步，再公开正确分支和理由。
子数组和 = prefix[r]-prefix[l-1],查 prefix-k 出现次数
核心机制：状态如何一步步变化
prefix mod K;map 存 mod 频次,同 mod 差为 K 倍数。
执行过程中持续维护：prefix mod、map。
正确性依赖以下不变量：(prefix[j]-prefix[i])%K==0 ⇔ 两前缀 mod K 相同。
面试时可以压缩为：前缀 mod K+哈希计数同余前缀,O(n)。
落到当前题，执行机制可以压缩为：prefix mod K;map 存 mod 频次,同 mod 差为 K 倍数。每一次更新都必须保持核心不变量，而不是只让样例碰巧得到正确答案。
一次状态转移为什么成立
集中观察一次选择、计算和状态写回，让变量变化与原因同时出现。
未命中,更新 map
正确性证明：为什么不会漏答案
初始化：算法开始时，全部合法候选仍在状态表示范围内；(prefix[j]-prefix[i])%K==0 ⇔ 两前缀 mod K 相同。
保持：执行“prefix mod K;map 存 mod 频次,同 mod 差为 K 倍数。”时，只删除已经能证明不可能的候选，并把新信息写回 prefix mod、map。
终止：没有待处理状态或达到命中条件时，当前可观察结果就是“同 mod 前缀差构成 K 倍数子数组个数。”。
完整执行过程
- 1题目与输入子数组和可被 K 整除个数。 因为：prefix mod K;map 存 mod 频次,同 mod 差为 K 倍数。
- 2prefix=4,查 -1 出现 0 次累加前缀,查补前缀。 因为：O(n) 哈希计数。
- 3预测下一步先不要看下一帧——根据当前不变量,预测算法接下来会怎么动。 因为：主动预测会暴露你对不变量的真实理解,比被动看动画有效得多。
- 4count[9] 更新前缀入库。 因为：供后续 j 查询。
- 5count[9] 更新前缀入库。 因为：供后续 j 查询。
- 6count[7] 更新前缀入库。 因为：供后续 j 查询。
- 7count[4] 更新前缀入库。 因为：供后续 j 查询。
- 8收尾与复杂度同 mod 前缀差构成 K 倍数子数组个数。 因为：时间 O(n) · 空间 O(1)。prefix mod K;map 存 mod 频次,同 mod 差为 K 倍数。
从输入完整走到可观察结果
从主例第一帧运行到答案，时间轴始终显示当前状态、因果解释和下一步。
子数组和 = prefix[r]-prefix[l-1],查 prefix-k 出现次数
把动画和 Go 代码逐行对应
代码窗口不会按容易漂移的固定数字行号硬绑动画，而是根据当前语义阶段， 在完整 Go 实现中定位选择、计算、写回或返回分支。当前变量与高亮行一起变化。
让每个动作都落到 Go 分支
重新执行关键分支，只显示当前代码附近窗口，并说明这行为什么在此刻运行。
子数组和 = prefix[r]-prefix[l-1],查 prefix-k 出现次数
完整 Go 提交代码与最小测试
func subarraysDivByK(nums []int, k int) int {
count := make([]int, k)
count[0] = 1
prefix, answer := 0, 0
for _, value := range nums {
prefix = (prefix + value) % k
if prefix < 0 { prefix += k }
answer += count[prefix]
count[prefix]++
}
return answer
}func main() {
// 1. 主例
// 输入：mode="subarray-sum-k", nums=[4,5,0,-2,-3,1], k=5
// 期望：同 mod 前缀差构成 K 倍数子数组个数。
//
// 2. 失败 / 未命中
// 检查：负数 mod 要 normalize 到 [0,K)。
//
// 3. 边界
// 空输入、单元素、最小合法规模，以及答案恰好落在边界的情况。
//
// 4. 迁移
// LC560 和为 K；LC525 连续数组
}正确性与复杂度
执行过程中只保留仍可能影响答案的状态。prefix mod K;map 存 mod 频次,同 mod 差为 K 倍数。
额外状态主要用于维护：prefix mod、map。
- • (prefix[j]-prefix[i])%K==0 ⇔ 两前缀 mod K 相同。
最容易写错的地方
负数 mod 要 normalize 到 [0,K)。
必须额外检查空输入、单元素、未命中或不可达情况，以及恰好落在边界的输入。
最后复盘：带走逻辑链
- 1题意子数组和可被 K 整除个数。
- 2重复每次重新计算区间会重复累加；前缀状态把区间信息变成两个历史状态的差或关系。
- 3优化prefix mod K;map 存 mod 频次,同 mod 差为 K 倍数。
- 4证明(prefix[j]-prefix[i])%K==0 ⇔ 两前缀 mod K 相同。
- 5复杂度时间 O(n)，空间 O(1)
- • LC560 和为 K
- • LC525 连续数组