Problem: 523. 连续的子数组和
文章目录
- 思路
- 解题方法
- 复杂度
- Code
思路
暴力的方法就是求出前缀和数组，然后枚举每个区间和，找到长度大于2且整除k的子区间，但是会超时.
暴力超时
//枚举左端点
for(int i = 0 ; i<n-1 ; i++ ) {
// 枚举子数组的长度
for(int j = i+2 ;j <=n ; j++ ) {
// 区间 [i,i+j]的和
if( (S[j] - S[i]) %k ==0 ){
// cout<< S[i+j] - S[i] <<endl;
return true ;
}
}
}解题方法
另一种方法是利用同余性质 ，
同余定理：如果两个整数m、n满足n-m能被k整除，那么n和m对k同余
假设我们的目标是求得 （区间 [i,j]的和）是满足整除k,
则 ,即存在一个整数n ,满足
两边同时除以 k , ,要使得n是整数，则
,
。
我们使用一个 哈希表存储前缀和对于 k的余数，第一次出现的就是左端点，第二次出现的就是右端点。
复杂度
- 时间复杂度:
- 空间复杂度:
Code
class Solution {
public:
bool checkSubarraySum(vector<int>& nums, int k) {
// (a-b) % k == 0
// a%k == b%k
int m = nums.size() ;
if(m < 2 ) return false ;
// 哈希表维护的 key : 余数 ,value ：前缀和对应的下标
unordered_map<int,int> mp ;
mp[0] = -1 ; // 前缀和为0的 下标为 -1
vector<int> perSum(m+1) ;
for(int i = 1 ; i <=m ; i ++ ) perSum[i] = perSum[i-1] + nums[i-1] ;
// s的下标取值 : [1,m]
int presum = 0 ;
for(int j = 1 ; j<=m ; j++ ) {
// 取出前缀和的余数
int r = perSum[j]%k ;
if(mp.count(r)) {
// 如果前缀和的余数存在,取出作为左端点
int i = mp[r] ;
if( j-i-1>=2 ) {
return true ;
}
}else{
mp[r] = j-1;
}
}
return false ;
}
};空间上还能优化，将求前缀和的过程省略，边求前缀和，边存哈希表的值。