算法:974.和可以被K整除的子数组
题目
链接:leetcode链接
思路分析(前缀和 + 同余定理)
首先,我们要了解一下什么是同余定理
同余定理:
如果(a - b)/ p = k …… 0
则 a % p == b % p
证明我写在草稿纸上,如下图:
初此之外,我们还需要理解一个问题
在C++/java中负数取模会怎么样呢?
比如 - 2 % 5等于多少呢?
按道理来说应该是3,但是C++/java里的答案是-2
这明显是需要进行修正的
如何进行修正呢?
我们只需要( a % p + p)% p
这样,无论是正数取模还是负数取模都不会出现问题。
OK,到这里前置知识讲完了,我们就正式开始讲思路了。
需要找一个子数组的和是k的倍数
那么只需要找两个区间的前缀和对k取模的余数相同即可。
和这道题的思路非常相似
传送门:560.和为k的子数组
我们利用滚动数组去求前缀和,
记录sum % k的余数
然后在[0,i-1]区间内去hash表中寻找一个区间的前缀和对k取模的结果与sum对k取模结果相同即可
将sum% k的余数放到hash表中(一定要是先查找在插入)
细节:
(1)什么时候插入hash表
一定要是先查找,在插入
(2)对于[0 , i]区间的和正好是K的倍数的情况如何处理
还是一样,我们先去把余数0提前先往hash表里插一个即可
具体原因可以查看和为k的子数组这篇文章
代码
//同余定理
int subarraysDivByK(vector<int>& nums, int k) {
int sum = 0,ret = 0;
unordered_map<int,int> hash;//hash表里面放余数
hash[0] = 1;//这个0依旧是存的余数
for(auto& e:nums)
{
sum += e;
int check = (sum % k + k) % k; // 对余数进行修正很关键
if(hash.count(check)) ret += hash[check];
hash[check]++;
}
return ret;
}
原文地址:https://blog.csdn.net/2303_78940834/article/details/142872188
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.kler.cn/a/348926.html 如若内容造成侵权/违法违规/事实不符,请联系邮箱:809451989@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.kler.cn/a/348926.html 如若内容造成侵权/违法违规/事实不符,请联系邮箱:809451989@qq.com进行投诉反馈,一经查实,立即删除!