面对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;
}