面对medium的题目始终抱有不可小觑的心。这次周赛顺利做好两道easy的以后 想如果能再拿下这道medium那么是不是可以进1000了？
给一个都是整数的数组，返回 和可以被K整除的子数组 数。
Given an array A of integers, return the number of (contiguous, non-empty) subarrays that have a sum divisible by K.
Example 1:
Input: A = [4,5,0,-2,-3,1], K = 5
Output: 7
Explanation: There are 7 subarrays with a sum divisible by K = 5:[4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]
Note:
数组最长30000。如果O(n^2) 那时间委实长久。
1 <= A.length <= 30000
-10000 <= A[i] <= 10000
2 <= K <= 10000
我依然写了个O(n^2)的算法。优化一下就是先循环的时候 把每个元素取模了。这样在求和的时候会不会加的更快？
public int SubarraysDivByK(int[] A, int K) {
int nums=0;
for(int i=0;i<A.Length;i++){
A[i]=A[i]%K;
if(A[i]==0) nums++;
}
for(int i=0;i<A.Length;i++){
int sum=A[i];
for(int j=i+1;j<A.Length;j++){
sum+=A[j];
if(sum%K==0) nums++;
}
}
return nums;
}

现在大家水平这么高了啊。我以前做对三道 速度稍微快点就200名附近

这题我说个思路吧。假设数组10个数。把前0，1，2...10个数的和分别记录下来。一共是11个和，第一个和是0。满足条件的数组，就是这11个和取其中两个，他们的差能被K整除。
所以，你建一个map，记录这11个和对K取模的余数，余数相等就是一个解。剩下就是对map扫一遍，找组合的数量。
总时间是线性的

var subarraysDivByK = function(A, K) {
var res=0;
for(var i=0;i<=A.length-1;i++){
if(A[i]%K==0){
res++;
}
var sum=A[i];
for(var j=i+1;j<A.length;j++){
sum+=A[j];
if(sum%K==0){
res++;
}
}
sum=0;
}
return res;
};
1 <= A.length <= 30000
-10000 <= A[i] <= 10000
2 <= K <= 10000
最近刷的人都
魔怔
了，上来先看看能不能暴力算法解决因为题目限制是之前有几道比30000还长的数组暴力算法是可以过的
结果超时还是看了答案