哪个网站可以免费制作h5/谷歌 chrome 浏览器

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

给定一个整数数组 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]

思路

之前刷560题时看到类似的思路，560题是求和为K的子数组，可以直接用前缀和来解决，该题改为和能被K整除的子数组，同样也可以用前缀和pre[i]表示数组从0到i的和，因此[j+1, …, i]的和可以用pre[i]-pre[j]表示，只要(pre[i] - pre[j]) % K == 0就存在一个子数组了。
然而还有一个同余定理，(pre[i] - pre[j]) % K == 0存在的条件是pre[i] % K == pre[j] % K。因而可以使用哈系表记录之前前缀和模K后值出现的次数，当前前缀和模K的值出现了多少次，答案子数组就增加多少个。

代码

class Solution {
public:int subarraysDivByK(vector<int>& A, int K) {unordered_map<int, int> m;m[0] = 1;int sum = 0;int ans = 0;for(int num : A) {sum += num;int res = (sum % K + K) % K; //负数模K需要纠正if(m.count(res)) {ans += m[res];}m[res]++;}return ans;}
};