题目链接:https://leetcode-cn.com/problems/subarray-sums-divisible-by-k
题目描述
分析
1. 嵌套for循环
遍历数组寻找能整除5的数之和，但是时间复杂度不符合题目要求
2. 同余定理
同余定理:[P(j)-P(i-1)]%K==0 <=> P(j)%K==P(i-1)%K,P(j)=a[0]+a[1+]..+a[j]
将余数和余数出现的次数存在map中，余数次数大于0之和即是题目答案
代码实现
public enum Q974 {
instance;
// O(n^2)
public int subarraysDivByK(int[] A, int K) {
int count=0;
for(int i=0;i<A.length;i++){
int sum=0;
for(int j=i;j<A.length;j++){
sum+=A[j];
if(sum%K==0){
count++;
}
}
}
return count;
}
// O(n)
public int subarraysDivByK1(int[] A, int K) {
// 同余定理:[P(j)-P(i-1)]%K==0 <=> P(j)%K==P(i-1)%K,P(j)=a[0]+a[1+]..+a[j]
// k:余数;v:次数（k:3,v:1 余数是3的K整除的数是1）
Map<Integer,Integer> map = new HashMap<>();
// 0%K==0
map.put(0,1);
int sum=0,count=0;
for(int i:A){
sum+=i;
int remainder=(sum%K+K)%K;//sum=13,K=5:-13%5=-3,-3+5=2,2%5=3
int remainderCount=map.getOrDefault(remainder,0);
count+=remainderCount;
map.put(remainder,remainderCount+1);
}
return count;
}
public static void main(String[] args) {
// assert 7
SystemUtil.print(Q974.instance.subarraysDivByK1(new int[]{4,5,0,-2,-3,1},5));
}
}
