题目链接:
连续的子数组和
有关题目
给你一个整数数组 nums 和一个整数 k ,编写一个函数来判断该数组是否含有同时满足下述条件的连续子数组:
1.子数组大小 至少为 2 ,且
2.子数组元素总和为 k 的倍数。
如果存在,返回 true ;否则,返回 false 。
如果存在一个整数 n ,令整数 x 符合 x = n * k ,则称 x 是 k 的一个倍数。
示例 1:
输入:nums = [23,2,4,6,7], k = 6
输出:true
解释:[2,4] 是一个大小为 2 的子数组,并且和为 6 。
示例 2:
输入:nums = [23,2,6,4,7], k = 6
输出:true
解释:[23, 2, 6, 4, 7] 是大小为 5 的子数组,并且和为 42 。
42 是 6 的倍数,因为 42 = 7 * 6 且 7 是一个整数。
示例 3:
输入:nums = [23,2,6,4,7], k = 13
输出:false
提示:
1 <&#61; nums.length <&#61; 10^5
0 <&#61; nums[i] <&#61; 10^9
0 <&#61; sum(nums[i]) <&#61; 2^31 - 1
1 <&#61; k <&#61; 2^31 - 1
题解
前缀和 &#43; 哈希表
思路&#xff1a;取自肥宅男孩
题解&#xff1a;参考官方题解
思路&#xff1a;
【同余定理】 【哈希表】【简化前缀和】
同余定理&#xff1a;如果两个整数m、n满足n-m能被k整除&#xff0c;那么n和m对k同余
即 ( pre(j) - pre (i) ) % k &#61;&#61; 0 则 pre(j) % k &#61;&#61; pre(i) % k
推导 &#61;> pre (i) % k &#61; (a0 &#43; a1 &#43; ... &#43; ai) % k &#61; (a0 % k &#43; a1 % k &#43; ... ai % k ) % k &#xff08;该推导在简化前缀和的时候有用&#xff0c;说明当前前缀和 % k 不会影响后面的前缀和 % k &#xff09;
哈希表 存储 Key &#xff1a;pre(i) % k
Value&#xff1a; i
遍历过程&#xff1a;
1.计算前缀和 pre( j ) % k
2.当pre(j) % k 在哈希表中已存在&#xff0c;则说明此时存在 i 满足 pre(j) % k &#61;&#61; pre(i) % k ( i < j )
3.HashMap里&#xff0c;已知Key&#xff0c;可以取到Value 即i的值&#xff0c; 最后 判断 j - i >&#61; 2 是否成立 即可
当 pre(j) % k 不存在于哈希表&#xff0c;则将 (pre(j) % k, j ) 存入哈希表
因在计算 pre(i) &#61; (pre(i-1) &#43; nums[i]) % k 时&#xff0c;pre(i) 只与上一个状态有关
故可以直接用变量pre 替代数组。 那么 求前缀和 % k 的公式就简化为 题解代码中的 remainder &#61; (remainder &#43; nums[i]) % k;
解释同余定理
取自宫水三叶
![在这里插入图片描述](https://img6.php1.cn/3cdc5/c369/bdf/4c926b59ecdd0c7f.jpeg)
代码一&#xff1a;
class Solution {
public:
bool checkSubarraySum(vector<int>& nums, int k) {
if(nums.size() < 2)
return false;
unordered_map<int,int> mp;
mp[0] &#61; -1;
int remainder &#61; 0;
for (int i &#61; 0; i < nums.size(); i&#43;&#43;)
{
remainder &#61; (remainder &#43; nums[i]) % k;
if (mp.count(remainder))
{
int preRemainder &#61; mp[remainder];
if (i - preRemainder >&#61; 2)
return true;
}
else
mp[remainder] &#61; i;
}
return false;
}
};
![在这里插入图片描述](https://img6.php1.cn/3cdc5/c369/bdf/b5ff32eae386b82f.jpeg)
代码二&#xff1a;
参考宫水三叶
class Solution {
public:
bool checkSubarraySum(vector<int>& nums, int k) {
int m &#61; nums.size();
vector<int> sum(m &#43; 1,0);
for (int i &#61; 1; i <&#61; m; i&#43;&#43;)
sum[i] &#61; sum[i - 1] &#43; nums[i - 1];
unordered_set<int> set;
for(int i &#61; 2; i <&#61; m; i&#43;&#43;)
{
set.insert(sum[i - 2] % k);
if (set.count(sum[i] % k))
return true;
}
return false;
}
};
![在这里插入图片描述](https://img6.php1.cn/3cdc5/c369/bdf/b5ff32eae386b82f.jpeg)
代码三&#xff1a;
滚动数组优化代码二
class Solution {
public:
bool checkSubarraySum(vector<int>& nums, int k) {
int m &#61; nums.size();
int ppre &#61; 0, pre &#61; nums[0];
unordered_set<int> set;
for (int i &#61; 2; i <&#61; m; i&#43;&#43;)
{
set.insert(ppre % k);
pre &#43;&#61; nums[i - 1];
if (set.count(pre % k))
return true;
ppre &#43;&#61; nums[i - 2];
}
return false;
}
};
![在这里插入图片描述](https://img6.php1.cn/3cdc5/c369/bdf/b5ff32eae386b82f.jpeg)