和可被 K 整除的子数组：同余配对
差能被 k 整除，当且仅当两端前缀和余数相同。按余数分组，两两一对就是一段。
子数组和 pre[j]−pre[i] 被 k 整除 ⇔ pre[i] ≡ pre[j] (mod k)。扫描时用哈希表统计每个余数出现次数：先把 freq[当前余数] 加进答案，再给这个余数 +1。空前缀余数 0 先记一次，整段和能被 k 整除时才数得到。Go 的负数取模可能为负，写成 ((pre%k)+k)%k。时间 O(n)。
这是 LeetCode 974. Subarray Sums Divisible by K。给你整数数组 nums 和整数 k，统计有多少个非空连续子数组的和能被 k 整除。数组里可以有负数和 0。
主例 nums = [4, 5, 0, −2, −3, 1]，k = 5。七段分别是 [5]、[5,0]、[5,0,−2,−3]、[0]、[0,−2,−3]、[−2,−3]、以及整段 [4,5,0,−2,−3,1]。答案 7。
枚举左右端点再求和取模是平方。缺的不是「整除」的定义，而是把整除翻译成前缀和之间的关系。本文先写出同余，再按余数把手例的 7 对一对点出来。
整除先换成两个前缀和同余
和 LC560 一样，子数组 [i, j) 的和是 pre[j]−pre[i]。这道题不要差等于某个 k，只要差是 k 的倍数。a−b = qk 当且仅当 a 与 b 除以 k 余数相同：两边同时减掉余数，剩下的都是 k 的倍数。
于是「和能被 k 整除的子数组」变成「有多少对前缀和下标 i < j，pre[i] 与 pre[j] 同余」。不必保存前缀和本身，只保存它模 k 的余数。
主例前两项 4、5，前缀和 4 与 9，余数都是 4。演示第二帧：9−4=5，正好一段 [5]。同余比「差再除一次」更直接，后面计数只看余数桶。
余数是唯一要记的前缀和可以很大，余数只有 0 到 k−1。哈希表的键是余数。整除问题先取模，再谈配对。
同余出现过几次，这一步就加几次
freq[m] 表示到目前为止余数 m 出现了几次。一开始 freq[0]=1，空前缀余数是 0。每读一个数：pre += x，m = ((pre%k)+k)%k，ans += freq[m]，然后 freq[m]++。先加后记，保证左端点在当前格子左边。同余出现 t 次，新来的这一个可以和前面 t 个各配一对，正好是组合数 C(t+1, 2) 相对 C(t, 2) 多出来的那 t 对。
用手走主例，k=5。4：余数 4，freq[4] 从 0 到 1，ans=0。5：pre=9，余数 4，加上已有的 1，ans=1，对应 [5]。0：pre=9，余数仍是 4，再加上 2，ans=3，对应 [5,0] 和 [0]。−2：pre=7，余数 2，第一次见，ans 仍 3。−3：pre=4，余数 4，前面 4 已经出现 3 次，ans=6。1：pre=5，余数 0，freq[0] 里那次空前缀被用上，整段入账，ans=7。
余数 4 一共出现 4 次，C(4,2)=6；余数 0 出现空前缀加最后一次，C(2,2) 按扫描累加是 1。合计 7。演示先停在 pre=9、余数 4 第一次配对，再停在扫完 ans=7。负数 −2、−3 若不把余数拨回正区间，Go 里 7%5 没问题，但 −1%5 会得到 −1，对不上 freq[4]。
Go：余数计数
func subarraysDivByK(nums []int, k int) int {freq := map[int]int{0: 1}pre, ans := 0, 0for _, x := range nums {pre += xm := ((pre % k) + k) % kans += freq[m]freq[m]++}return ans}
1freq[0]=1 让「从开头到当前、和本身能被 k 整除」数得到。主例最后 pre=5 靠的就是它。
2只累加前缀和，不需要真正的前缀数组。
3((pre%k)+k)%k 把负数余数拨回 0..k-1。少了这句，−2、−3 会进错桶。
4先加 freq[m] 再 ++。主例第三次见到余数 4 时，一次加上 2，对应 [5,0] 和 [0]。
5每个位置只更新一个余数桶，总时间线性。
总结
同余的前缀和两两一对。主例余数 4 出现四次贡献 6，余数 0 贡献 1，共 7。
- 整除先改写成前缀和同余，不要对每个子数组现场求和。
- 扫描累加 freq[m] 等价于每个余数桶里做 C(次数, 2)。
- Go 的 % 对负数可能为负，必须拨回非负再当键。