523. 连续的子数组和 （前缀和 + 同余性质+哈希）

//枚举左端点
        for(int i = 0 ; i

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13

解题方法

另一种方法是利用同余性质 ，
同余定理：如果两个整数m、n满足n-m能被k整除，那么n和m对k同余

假设我们的目标是求得 $$S[j]-S[i-1]$$（区间 [i,j]的和）是满足整除k,
则$$S[j]-S[i-1]\%k==0$$ ,即存在一个整数n ,满足 $$S[j]-S[i-1]=n\ast k$$
两边同时除以 k , $$\frac{S[j]}{k}-\frac{S[i-1]}{k}=n$$ ,要使得n是整数，则 $$S[j]\%k==0$$ ,$$S[i-1]\%k==0$$ 。
我们使用一个 哈希表存储前缀和对于 k的余数，第一次出现的就是左端点，第二次出现的就是右端点。

复杂度

• 时间复杂度:

$O(n)$

• 空间复杂度:

$O(n)$

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 ; 
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

空间上还能优化，将求前缀和的过程省略，边求前缀和，边存哈希表的值。