【算法】前缀和算法——和可被K整除的子数组

题解：和可被K整除的子数组(前缀和算法)

1.题目

题目链接：LINK

2.前置知识

2.1同余定理

注：这里的‘/’代表的是数学中的➗

同余定理： (a - b) / p = k … 0 —> a % p = b % p;

证明如下：

原式：(a - b)/p = k

两边同乘p：a-b = k*p

移项：a = b + k*p

两边同模p：a % p = (b + k*p)%p = b%p

即：(a - b) / p = k … 0 --> a % p = b % p

结论：在本题中，有了这个定理这就表明了找到了

前缀和sum%p == x%p 等价于 (sum - x) % k = 0

2.2CPP中‘%’的计算方式与数学‘%’的差异 及其 修正

CPP%：负数 % 正数 = 负数

数学%：负数 % 正数 = 正数

显然，在本题中，题意指的是数学取模。

CPP%修正：

在a是负数的情况下：负数(a) % 正数§ = 负数 --> a % p + p*1

在a是正数/负数情况下：负数(a) % 正数§ = 负数 --> (a % p + p) % p

结论：在本题中，我们可以用上面数学公式来进行修正CPP取模值

2.3题目思路

与，和为k的子数组之和(前缀和算法)一致，链接：LINK

3.代码示例

class Solution {
public:
    int subarraysDivByK(vector<int>& nums, int k) 
    {
        unordered_map<int,int> hash;
        hash[0 % k] = 1;
        int ret = 0;
        int sum = 0;
        //统计前缀和
        for(auto& num: nums)
        {
            sum+=num;
            int r = (sum % k + k) % k;
            //判断哈希表中是否有这个数字
            if(hash.count(r)) ret += hash[r];
            //把这个前缀和入到哈希表中
            hash[r]++;
        }
        return ret;
    }
};

4.总结

感觉理解那一串数学公式是比较重要的，其他就跟上一道题(LINK)一摸一样了。

EOF