题目描述：

和可被 K 整除的子数组
给定一个整数数组 A，返回其中元素之和可被 K 整除的（连续、非空）子数组的数目。
1 <= A.length <= 30000
-10000 <= A[i] <= 10000
2 <= K <= 10000

输入示例：

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整除的连续子数组的数目，第一反应就是先求出前缀和，前缀和相减即为区间和，区间和对K取模为0，则ret++。这个思路没问题，但是会超时....然后再观察一下前缀和，我们可以发现对前缀和取模后，如果两个前缀和相等，那么这个区间一定是符合要求的，所以统计前缀和次数，然后排列组合。具体代码如下~

代码实现：

class Solution {
    public int subarraysDivByK(int[] A, int K) {
        int[] countSum=new int[K];
        int sum=0;
        countSum[0]=1;
        for(int i=0;i<A.length;i++){
            sum=((sum+A[i])%K+K)%K;
            countSum[sum]++;
        }
        int ret=0;
        for(int i=0;i<K;i++){
            ret+=(countSum[i]*(countSum[i]-1))/2;
        }
        return ret;
    }
}