算法：974.和可以被K整除的子数组

题目

链接:leetcode链接

思路分析（前缀和 + 同余定理）

首先，我们要了解一下什么是同余定理

同余定理：
如果（a - b）/ p = k …… 0
则 a % p == b % p

证明我写在草稿纸上，如下图：

初此之外，我们还需要理解一个问题
在C++/java中负数取模会怎么样呢？
比如 - 2 % 5等于多少呢？
按道理来说应该是3，但是C++/java里的答案是-2
这明显是需要进行修正的

如何进行修正呢？
我们只需要（ a % p + p）% p
这样，无论是正数取模还是负数取模都不会出现问题。

OK，到这里前置知识讲完了，我们就正式开始讲思路了。

需要找一个子数组的和是k的倍数
那么只需要找两个区间的前缀和对k取模的余数相同即可。

和这道题的思路非常相似
传送门：560.和为k的子数组

我们利用滚动数组去求前缀和，
记录sum % k的余数
然后在[0,i-1]区间内去hash表中寻找一个区间的前缀和对k取模的结果与sum对k取模结果相同即可
将sum% k的余数放到hash表中（一定要是先查找在插入）

细节：
（1）什么时候插入hash表
一定要是先查找，在插入
（2）对于[0 , i]区间的和正好是K的倍数的情况如何处理
还是一样，我们先去把余数0提前先往hash表里插一个即可
具体原因可以查看和为k的子数组这篇文章

代码

//同余定理
    int subarraysDivByK(vector<int>& nums, int k) {
        int sum = 0,ret = 0;
        unordered_map<int,int> hash;//hash表里面放余数

        hash[0] = 1;//这个0依旧是存的余数
        for(auto& e:nums)
        {
            sum += e;
            int check = (sum % k + k) % k; // 对余数进行修正很关键
            if(hash.count(check))  ret += hash[check]; 
            hash[check]++;
        }

        return ret;
    }