使用 oh-my-zsh

974、和可被K整除的子数组

给定一个整数数组 A，返回其中元素之和可被 K 整除的（连续、非空）子数组的数目。

 

示例：

输入：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]

提示：

• 1 <= A.length <= 30000
• -10000 <= A[i] <= 10000
• 2 <= K <= 10000

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

题解

1、前缀和

计算数组的前缀和，对于每一位的前缀和，先判断是否可以整除K,然后从左侧依次减去元素，判断是否可以被整除。

暴力枚举——超时

class Solution {
    public int subarraysDivByK(int[] A, int K) {
        int[] accA = new int[A.length];
        int count = 0;
        for (int i = 0;i < A.length;i++) {
            accA[i] += A[i];
            if (i > 0) {
                accA[i] += accA[i - 1];
            }
        }

        for (int i = 0;i < A.length;i++) {
            // 0~i [0,i]
            if (accA[i]%K == 0) {
                count++;
            }
            // j~i ==> (j,i]
            for (int j = 0;j < i;j++) {
                if ((accA[i] - accA[j]) % K == 0) {
                    count++;
                }
            }
        }

        return count;
    }
}

1.1、哈希表 + 逐一统计

$$
(P[j] - P[i - 1]) % K = 0 \

可变形为：P[j] % K = P[i - 1] % K
$$
这样，可以统计每一个位置的前缀和，前缀和相同的两个位置对应的连续数组一定可以被K整除

class Solution { 
    public int subarrayDivByK(int[] A,int K) {
        Map<Integer,Integer> record = new HashMap<>();
        // 前缀和本身可以被K整除
        record.put(0, 1);
        int sum = 0,ans = 0;
        for (int a : A) {
            sum += a;
            // 将取模结果变为正数，+K不影响结果
            int mod = (sum % K + K) % K;
            // 获取mod相同的出现次数
            int same = record.getOrDefault(mod, 0);
            ans += same;
            // 累加统计次数
            record.put(mod,same + 1);
        }
        return ans;
    }
}

• 直接用数组作为hash表

class Solution {
    public int subarraysDivByK(int[] A, int k) {
        int[] m = new int[k];
        m[0] = 1;
        int count = 0,sum = 0;
        for (int a: A ) {
            sum = (sum + a ) % k;
            if(sum < 0) {
                sum += k;
            }
            count += m[sum];
            m[sum]++;
        }
        return count;
    }
}

1.2、哈希表 + 单次统计

考虑方法一中的思路，我们可以在遍历只维护哈希表。在遍历结束后，我们再遍历哈希表，用排列组合的方法来统计答案。

class Solution {
    public int subarraysDivByK(int[] A, int K) {
        Map<Integer, Integer> record = new HashMap<>();
        record.put(0, 1);
        int sum = 0;
        for (int elem: A) {
            sum += elem;
            // 注意 Java 取模的特殊性，当被除数为负数时取模结果为负数，需要纠正
            int modulus = (sum % K + K) % K;
            record.put(modulus, record.getOrDefault(modulus, 0) + 1);
        }

        // 进行排列组合计算，两两握手
        int ans = 0;
        for (Map.Entry<Integer, Integer> entry: record.entrySet()) {
            ans += entry.getValue() * (entry.getValue() - 1) / 2;
        }
        return ans;
    }
}

// 作者：LeetCode-Solution
// 链接：https://leetcode-cn.com/problems/subarray-sums-divisible-by-k/solution/he-ke-bei-k-zheng-chu-de-zi-shu-zu-by-leetcode-sol/

• 优雅实现

class Solution {
    public int subarraysDivByK(int[] A, int K) {
        // 计算第一个的余数
        A[0] = A[0] % K;
        // 统计前缀和的余数
        for (int i = 1;i < A.length;i++) A[i] = (A[i-1] + A[i]) % K;
        // 统计余数相同的个数
        int[] count = new int[K];
        count[0]++;
        for (int x : A) count[(x % K + K) % K]++;
        // 计算一共有多少个
        int ans = 0;
        for (int y : count) ans = ans + y * (y - 1) / 2;
        return ans;
    }
}

---

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com