LeetCode 974. 和可被 K 整除的子数组

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

 

上一篇:Python 日期时间datetime 加一天,减一天,加减一小时一分钟,加减一年一月,时区转换


下一篇:Python中datetime模块的常用功能