每天一道leetcode 和可被 K 整除的子数组(前缀和+同余定理+hashmap)

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

难度中等80收藏分享切换为英文关注反馈

给定一个整数数组 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. 1 <= A.length <= 30000
2. -10000 <= A[i] <= 10000
3. 2 <= K <= 10000

答：

int subarraysDivByK(int* A, int ASize, int K){
    int addr=0;
    int ret=0;
    int temp[K];
    for(int i=0;i<K;i++){temp[i]=0;}
    temp[0]=1;
    for(int i=0;i<ASize;i++)
    {
        addr+=A[i];
        int mod=(addr%K+K)%K;
        if(temp[mod])
        {
            ret+=temp[mod];
        }
        temp[mod]++;
    }
    return ret;
}

解析：

• 同余定理：

2个不同的整数a、b，被一个整数m相除时，得到相同的余数，那么我就可以称a、b同余。

因为a、b同余所以当他们相减时，余数就抵消掉了，剩下的那部分就是能被m整除的。

• 所以利用前缀和，我们只要叠加余数相同的前缀和的个数就可以了，具体的可以用hashmap，也可以用数组标记

官方解析：

https://leetcode-cn.com/problems/subarray-sums-divisible-by-k/solution/he-ke-bei-k-zheng-chu-de-zi-shu-zu-by-leetcode-sol/