https://leetcode-cn.com/problems/subarray-sums-divisible-by-k/

 

第一眼，子数组问题，以为是滑动窗口，但是仔细想想做不了。

然后看了眼数据规模 30000，私以为可以暴力法过，但是死在了第69个测试用例。

class Solution {
    public int subarraysDivByK(int[] A, int K) {
        int count = 0;
        int temp = 0;
        for(int i = 0; i < A.length; i++){
            for(int j = i; j < A.length; j++){
                temp += A[j];
                if(temp % K == 0){
                    count++;
                }
            }
            temp = 0;
        }
        return count;
    }
}

然后瞄了一眼标签，发现哈希表这个tag，再加上这个题有点想前几天做过的前缀和的题，故使用前缀和思想。

我一开始是用前缀和找到i,j之间的和，然后判断这个和是否能被K取整，但是做出来分析一下时间复杂度还是O(n^2)，一样会TLE

后来实在没办法了，瞄了一眼评论区才发现大佬们用的是余数来判断的。。

    public int subarraysDivByK(int[] A, int K) {
        int count = 0;
        HashMap<Integer,Integer> map = new HashMap<>();
        int temp = 0;
        map.put(0,1);
        for(int i = 0; i < A.length; i++){
            temp += A[i];
            //这个步骤是将负数转换成正数，为什么要这么操作呢？因为小于0的数字，除余之后得到的还是小于0。但是余数为-5 和余数为5其实可以归为一类。
            int curMod = ((temp % K) + K) % K;
            int preMod = map.getOrDefault(curMod,0);
            count += preMod;
            map.put(curMod,map.getOrDefault(curMod,0)+1);
        }
        return count;
    }

这个其实又是数学问题，我的数学是真的垃圾啊。。

同余定理：如果两个整数 a, b 满足 (a-b)%K == 0，那么有 a%K == b%K。
由此可知,如果 i，j 满足 (prefix(j) - prefix(i-1))%K == 0，那么有 prefix(i)%K == prefix(i-1)%K。
故，可以扫描一遍前缀和 prefix，利用 map 统计所有余数出现的次数，然后遍历 map 利用组合公式C(n,m) = n!/((n-m)!*m!) 来计算答案。
此时时间复杂度降到了 O(n)。

这里因为有K这个固定的数，我们就可以将map转换成数组来节省时间

    public int subarraysDivByK2(int[] A, int K) {
        int[] map = new int[K];
        ++map[0];
        int prefix = 0, res = 0;
        for (int a : A) {
            prefix = (a + prefix) % K;
            if (prefix < 0) prefix += K;
            res += map[prefix]++;
        }
        return res;
    }