从此无心爱良夜
任他明月下西楼
一开始我就想到了前缀和，通过前缀和的差可以很快确定某段连续元素的和，能够被K整除的和就能满足条件。
不过问题就在于这样子的复杂度是O(N2)，我感觉是过不去的。
看了评论区才发现同余定理这个“显而易见”的定理。
简单来说就是如果(a - b) % k == 0，则a % k == b % k。
如果存在多个取模相等的数，则按照顺序两两组合一下：cnt * (cnt - 1) / 2。
需要注意的就是负数被正数取余后，得到的是负数，应将其转化成正数：(a % K + K) % K，否则无法对应。
这个时候只要对不同余数进行计数，然后加上不同余数的cnt * (cnt - 1) / 2即可。
这时候hash表就不需要用map了，直接用数组或者vector就行了。
class Solution {
public:
int subarraysDivByK(vector<int> &A, int K) {
int presum = 0;
vector<int> hash(K);
hash[0] = 1;
for (const int &it : A) {
presum += it;
hash[(presum % K + K) % K]++;
}
int ans = 0;
for (const auto &it : hash) {
if (it > 1) {
ans += it * (it - 1) / 2;
}
}
return ans;
}
};
