本文主要是介绍在做题在学习(60):和可被K整除的子数组,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
974. 和可被 K 整除的子数组 - 力扣(LeetCode)
解法:前缀和 + 哈希表 + 同余定理
同余定理:
而此题要求返回能被k整除(%k = 0)的子数组的个数,如下图:
把问题转化为——> 有多少个前缀和的余数 == sum%k ???
细节
1.c++中的[整数 % 负数]转化
负数 % 正数 = 负数 ——修正——> a % p + p ——正负统一——> (a % p + p) % p
2.默认哈希表中 hash[0] = 1
因为0 % k 一定 == 0
3.前缀和的余数什么时候丢入哈希表?
因为放进去的是前缀和的余数,放[0,i]的话,到了[0,i+1]就会重复,所以到i下标时,先放入[0,i-1]的前缀和的余数,再加入自己。
4.不用真的创建一个前缀和数组
dp[i] = sum + nums[i] ,所以只需要一个sum代表前一次的前缀和,每次算完前缀和,把sum更新就行了。
class Solution
{
public:int subarraysDivByK(vector<int>& nums, int k) {unordered_map<int,int> hash;hash[0] = 1;int sum = 0,count = 0,rest = 0;for(auto e : nums){sum += e;rest = (sum % k + k) % k;//这里的判断就是先判断前面位置的前缀和的余数if(hash.count(rest))count += hash[rest];//到这里,再把当前i位置的前缀和的余数放入哈希表hash[rest]++;}return count;}
};
这篇关于在做题在学习(60):和可被K整除的子数组的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!