題目
給定一個整數(shù)數(shù)組 A，返回其中元素之和可被 K 整除的（連續(xù)玩荠、非空）子數(shù)組的數(shù)目辛块。
示例
輸入：A = [4,5,0,-2,-3,1], K = 5
輸出：7
解釋：
有 7 個子數(shù)組滿足其元素之和可被 K = 5 整除：
[4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]
題目分析
前綴和雙層遍歷
最直觀的思路是先求出前綴和數(shù)組，然后遍歷前綴和數(shù)組：
int subarraysDivByK(int* A, int ASize, int K){
int* ans = (int*)calloc(ASize, sizeof(int));
int count = 0;
int temp = 0;
for (int i = 0; i < ASize; i++) {
temp += A[i];
ans[count++] = temp;
}
int res = 0;
for (int i = 0; i < ASize - 1; i++) {
if (ans[i] % K == 0) res++;
for (int j = i + 1; j < ASize; j++) {
if ((ans[j] - ans[i]) % K == 0) res++;
}
}
if (ans[ASize - 1] % K == 0) res++;
return res;
}
這樣的時間復(fù)雜度是O(n^2)槐沼，會超時曙蒸。
前綴和+哈希表（同余定理）
同余定理：給定一個正整數(shù)m，如果兩個整數(shù)a和b滿足a-b能夠被m整除岗钩，即(a-b)/m得到一個整數(shù)纽窟，那么就稱整數(shù)a與b對模m同余，記作a≡b(mod m)兼吓。對模m同余是整數(shù)的一個等價關(guān)系臂港。
也就是說，如果兩個數(shù)對K的余數(shù)相同视搏，則兩數(shù)之差能被K整除审孽。
因此，我們可以用哈希表儲存數(shù)組中每個數(shù)字對K的余數(shù)浑娜，遇到相同余數(shù)則結(jié)果+1佑力。
class Solution {
public:
int subarraysDivByK(vector<int>& A, int K) {
unordered_map<int, int> m = {{0, 1}};
int sum = 0, ans = 0;
for (auto a : A) {
sum += a;
int mod = (sum % K + K) % K;
if (m.count(mod)) {
ans += m[mod];
}
m[mod]++;
}
return ans;
}
};
