同余定理
给定一个整数m, 如果有两个整数a和b, 并且满足 (a - b) 能够被 m 整除, 即 (a - b) / m 可以得到一个整数, 那么整数 a 与 b 对 m 是同余的. 记做: a ≡ b (mod m).(表示a和b除以m的余数相等)
有啥用? 同余是两个整数的等价关系. 即: 在某种问题上, 你可以把一个很大的数用一个与它同余的非常小的数替换.
比如: 求 (1999^2000) % 5 = ? 怎么算呢?
因为: 1999 - (-1) = 2000, 2000 可以被5整除, 所以 1999 ≡ -1 (∈ 5).
又因为同余性质: a ≡ b (∈ m ) => a ^ n ≡ b ^ n (∈ m )
所以: (1999^2000) % 5 => ((-1) ^ 2000) % 5 = 1
是不是突然觉的同余很有用呢? 其实我们平时做分布式开发的时候很多场景都会用到同余的概念, 比如负载均衡LB的hash取模.
问题描述
给定一个整数数组 A，返回其中元素之和可被 K 整除的（连续、非空）子数组的数目。
输入：A = [4,5,0,-2,-3,1], K = 5
输出：7
解释：
有 7 个子数组满足其元素之和可被 K = 5 整除：
[4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]
直接看上面的用例, 有点懵. 先抛弃用例. 我们分析问题.
题目关键字: (连续, 非空)子数组, 元素, 之和, 被K整除, 的数目.
- (连续, 非空)子数组
我们假设一个子数组从i开始, 到j结束. 记做A[i, j], 其中 i < j.
- 元素
就是数组中的一个值, 我们记做: A[n], n ∈ (0, length-1) n为数组的下标, 从0开始到数组长度-1为止.
- 之和
我们把子数组的元素之和记做: sum, 当一个子数组从 i 开始到 j结束, 那么它的元素之和就记做: sum(i, j), 其中(i < j).
怎么求sum(i, j)的元素之和呢? 直接想到到就是把i到j中的每个元素相加即可, 即: A[i] + A[i+1] + … + A[j]. 可以是可以, 但是我们需要找寻算法. 所以这里使用前缀思想.
子数组A[0, i-1]为数组从0到i-1的前缀子数组. 它的元素之和用P[0, i-1]表示. 即: P[0, i-1] = A[0] + A[1] + A[2] + A[3] + … + A[i-1].
子数组A[0, j]为数组从0到j的前缀子数组. 它的元素之和用P[0, j]表示. 即: P[0, j] = A[0] + A[1] + A[2] + A[3] + … + A[j].
如果我用 P[0, j] - P[0, i-1] 会得到什么呢?
P[0, j] = A[0] + A[1] + A[2] + A[3] + ... + A[i-1] + A[i] + A[i+1] +...+A[j]
- P[0, i-1] = A[0] + A[1] + A[2] + A[3] + ... + A[i-1]
= 0+0+0+...+A[i]+...+A[j]
= A[i]+...+A[j]
= sum(i, j)
所以 sum(i, j) = P[0, j] - P[0, i-1]
- 被K整除, 的数目.
能被K整除, 意为着 % K == 0. 也就是说一个从i到j的子数组之和 sum(i, j) % K == 0.
sum(i, j) = P[0, j] - P[0, i-1].
当 sum(i, j) % K == 0, 那么 (P[0, j] - P[0, i-1]) % K == 0. 重点来了, 像不像同余定理的描述.
如果有两个整数a和b, 并且满足 (a - b) 能够被 m 整除, 即 (a - b) / m 可以得到一个整数, 那么整数 a 与 b 对 m 是同余的.
P[0, j] 与 P[0, i-1] 对 K 是同余的. 即: P[0, j] % K == P[0, i] % K
任意数字对K取余的值, 都在[0, k-1]的区间内
但是那又怎样呢??? 同余, 同余, 同余. 就是余数相等的意思.
那么当i从0到length-1的过程中, 即P[0, 0], P[0, 1], P[0, 2],…, P[0, length-1]中, 我们对它们取余. 当出现取余相同的数目>1以上的时候, 我们就把这些次数累计起来. 最后就是题目要求的的数目.
难点
难点1: 为啥可以通过取余就能获取题目要求的数目呢?
其实这里拿取余个数是有要求的, 必须有两个或两个以上出现相同余数的情况才能记入统计的数目中.
因为根据公式:
- sum(i, j) % K == 0, 那么 (P[0, j] - P[0, i-1]) % K == 0
- (P[0, j] - P[0, i-1]) % K == 0, 推出 P[0, j] % K == P[0, i-1]) % K
所以相同取余的数量必须在两个以上时才能记入统计的数目.
难点2: 为啥初始化时需要给map[0]=1, 或者数组[0]=1呢?
我开始也没有想明白. 我们在仔细看下算法.
我们的算法是通过下面推导出来的.
sum(i, j) % K == 0
-> (P[0, j] - P[0, i-1]) % K == 0
-> P[0, j] % K == P[0, i-1]%k
根据公式, 我们的map中, 只有取余相同的情况出现两次或两次以上才会被统计到. 注意重点是两次及两次以上的时候才会被统计到.
而当一个子数组之和可以直接被K整除, 即: P[0, i-1]%k==0时, 我们还需等待第二个相同取余==0的子数组出现吗?
肯定是不需要的, 只要出现能被整除的子数组就应该直接被统计, 因为它本身就直接符合题目要求啊.
而当P[0, i-1]%k==0时, 我们得到的key=0, 所以我们在初始化时需要给map[0]=1, 或者数组[0]=1, 这样当第一次出现的时候, 我们就可以统记了.
难点3: 为啥要这样写(sum % K + K) % K
在数学中(sum % K + K) % K 等同 sum % K.
但是在某些编程中sum % K的值会是负数. 如下图:
[image:9429F4E6-70A5-40AC-833C-C26C5AAA17F6-7320-000141F850B04E6B/10FC49D5-7640-4541-AA34-E74095444E2D.png]
那么如果我们不做处理, 意为着有可能会出现漏统计值的情况.
比如 P[0, x1] = 5, P[0, x1] % 3 == 2, P[0, x2] = -7, P[0, x2] % 3 = -1, 如果在Java中不做处理, 则会漏统计.
处理的方式就是加一个取余的值, sum % K -> (sum % K + K) % K
为啥? 还是可以根据同余定理推导.
定理中设 (a-b) / m 可以得到一个整数, 那么 a % m == b % m.
设: a = (sum%k + k), b = sum%k, m = k 那么: a-b == sum%k + k - sum%k == k, 而 k / k == 1, 所以: a % m -> (sum%k + k)% k == b % m == sum%k%k 因为: sum%k = x, 而x的值在[0, k-1]区间内, 所以: sum%k%k = x%k 还是x, 即:[0, k-1] 所以: sum % K -> (sum % K + K) % K
给一个数加n个K, 取余的结果都一样.
参考
#01 Blog/算法相关#