刚开始用前缀和的方法试试,会超时
class Solution {
public:
int subarraysDivByK(vector<int>& nums, int k) {
int size = nums.size();
vector<int> preSum(size + 1, 0);
for (int i = 1; i <= size; i++)
preSum[i] = preSum[i - 1] + nums[i - 1];
int cnt = 0;
for (int i = 1; i <= size; i++)
for (int j = 0; j < i; j++)
if ((preSum[i] - preSum[j]) % k == 0)
cnt++;
return cnt;
}
};
然后和
【中等】和为K的子数组
一样,也用散列表优化
class Solution {
private:
map<int, int> mp;
public:
int subarraysDivByK(vector<int>& nums, int k) {
int sum = 0, cnt = 0;
mp[0] = 1;
for (int i = 0; i < nums.size(); i++)
{
sum += nums[i];
int n = (sum % k + k) % k;
//(sum % k + k) % k防止出现下标为负数的情况
if (mp[n] > 0)
cnt += mp[n];
mp[n]++;
}
return cnt;
}
};
用例子讲解一下我做这题的思路(思维比较发散,想到哪说到哪)
A = [4,5,0,-2,-3,1], K = 5
累加和对k求余,如果求到的余数出现过,那么一定可以在能求出这个余数的一个数或一串数后面找到和是k的倍数的子串。
比如[4, 1, 2, 2],和为9,对5求余得4,可以求出余数是4的数就是第一个4,而这个数后面一定能找到的和为5的子串[1, 2, 2]。(可以求出余数是4的要么是第一个数,要么是前面的一串数,所以得到和为5的子串一定会在第一个数或一串数后面,一定是连续的)
举个小例子细讲
a = [4, 5, 0] k = 5
第一个数得到余数4,mp[4] = 1。
然后4+5得9,9的余数是4,而mp[4]=1表明4出现过了,说明5一定可以被k整除,cnt += mp[4], 结果为1。
之后mp[4]会加1,原因是如果加上后面的数求余之后也是4,说明自己也能被k整除。但是别忘了,5能被k整除,自己也能被k整除,自然5和我加起来也能被k整除,所以加1是为了这个。
说来就来,0还正好能被5整除,所以此时cnt += mp[4]后cnt就是3了,包括了三种情况。
然后mp[4]会再再加1,原因再说一遍:如果加上0后面的数x后求余还是4,说明[5]、[0]、[x]、[5, 0]、[0, x]、[5, 0, x]都能被k整除,cnt加上mp[4]后就变成了6,包括了这6种情况