974、和可被K整除的子数组
给定一个整数数组 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]
提示：
1 <= A.length <= 30000-10000 <= A[i] <= 100002 <= K <= 10000
链接：https://leetcode-cn.com/problems/subarray-sums-divisible-by-k
题解
1、前缀和
计算数组的前缀和，对于每一位的前缀和，先判断是否可以整除K,然后从左侧依次减去元素，判断是否可以被整除。
暴力枚举——超时
class Solution {
public int subarraysDivByK(int[] A, int K) {
int[] accA = new int[A.length];
int count = 0;
for (int i = 0;i < A.length;i++) {
accA[i] += A[i];
if (i > 0) {
accA[i] += accA[i - 1];
}
}
for (int i = 0;i < A.length;i++) {
// 0~i [0,i]
if (accA[i]%K == 0) {
count++;
}
// j~i ==> (j,i]
for (int j = 0;j < i;j++) {
if ((accA[i] - accA[j]) % K == 0) {
count++;
}
}
}
return count;
}
}
1.1、哈希表 + 逐一统计
$$
(P[j] - P[i - 1]) % K = 0 \
可变形为：P[j] % K = P[i - 1] % K
$$
这样，可以统计每一个位置的前缀和，前缀和相同的两个位置对应的连续数组一定可以被K整除
class Solution {
public int subarrayDivByK(int[] A,int K) {
Map<Integer,Integer> record = new HashMap<>();
// 前缀和本身可以被K整除
record.put(0, 1);
int sum = 0,ans = 0;
for (int a : A) {
sum += a;
// 将取模结果变为正数，+K不影响结果
int mod = (sum % K + K) % K;
// 获取mod相同的出现次数
int same = record.getOrDefault(mod, 0);
ans += same;
// 累加统计次数
record.put(mod,same + 1);
}
return ans;
}
}
- 直接用数组作为hash表
class Solution {
public int subarraysDivByK(int[] A, int k) {
int[] m = new int[k];
m[0] = 1;
int count = 0,sum = 0;
for (int a: A ) {
sum = (sum + a ) % k;
if(sum < 0) {
sum += k;
}
count += m[sum];
m[sum]++;
}
return count;
}
}
1.2、哈希表 + 单次统计
考虑方法一中的思路，我们可以在遍历只维护哈希表。在遍历结束后，我们再遍历哈希表，用排列组合的方法来统计答案。
class Solution {
public int subarraysDivByK(int[] A, int K) {
Map<Integer, Integer> record = new HashMap<>();
record.put(0, 1);
int sum = 0;
for (int elem: A) {
sum += elem;
// 注意 Java 取模的特殊性，当被除数为负数时取模结果为负数，需要纠正
int modulus = (sum % K + K) % K;
record.put(modulus, record.getOrDefault(modulus, 0) + 1);
}
// 进行排列组合计算，两两握手
int ans = 0;
for (Map.Entry<Integer, Integer> entry: record.entrySet()) {
ans += entry.getValue() * (entry.getValue() - 1) / 2;
}
return ans;
}
}
// 作者：LeetCode-Solution
// 链接：https://leetcode-cn.com/problems/subarray-sums-divisible-by-k/solution/he-ke-bei-k-zheng-chu-de-zi-shu-zu-by-leetcode-sol/
- 优雅实现
class Solution {
public int subarraysDivByK(int[] A, int K) {
// 计算第一个的余数
A[0] = A[0] % K;
// 统计前缀和的余数
for (int i = 1;i < A.length;i++) A[i] = (A[i-1] + A[i]) % K;
// 统计余数相同的个数
int[] count = new int[K];
count[0]++;
for (int x : A) count[(x % K + K) % K]++;
// 计算一共有多少个
int ans = 0;
for (int y : count) ans = ans + y * (y - 1) / 2;
return ans;
}
}
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com
