974. Subarray Sums Divisible by K

发表于 | 分类于 | 浏览 次

Given an array A of integers, return the number of (contiguous, non-empty) subarrays that have a sum divisible by K.

Example 1:

1
2
3
4
Input: A = [4,5,0,-2,-3,1], K = 5
Output: 7
Explanation: There are 7 subarrays with a sum divisible by K = 5:
[4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]

解法一: hashmap

和leetcode 560、523相似的思路。
使用hashmap来记录当前满足条件的子数组个数。
当以数组中第i个元素nums[i]结尾的子数组的和为sum，那么在hashmap中记录了以nums[0], nums[1],…,nums[i-1]结尾的子数组的和。但是这里记录的和是对K取余后的。
若nums[0] = sum1，nums[0] +…+ nums[j] = sum1 + n * K，则(nums[0] +….+ nums[j]) % K = sum1，即这两个子数组和取余后都等于同一个数，即子数组nums[1] + … + nums[j] = K。
但是需要注意的是：当子数组和为负数时，需要不断加上K直到子数组和为正数。

例如: [7, 4, -10] 5
i = 0, sum = 7, mp[0] = 1(空数组的和为0)
sum = 7 % 5 = 2 mp[2] = 0， 因此，尚不存在以nums[0]结尾的子数组和为5的倍数

i = 1, sum = (2 + 4 ) % 5 = 1
mp[0] = 1, mp[2] = 1
又mp[1] = 0 ，因此，尚不存在以nums[1]结尾的子数组和为5的倍数
mp[1] = 1

i = 2, sum = (1+-10) % 5 = -9 % 5 = -4, sum = (-4+5)%5 = 1
又mp[1] = 1，因此，存在一个以nums[2]结尾的子数组和为5的倍数

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int subarraysDivByK(vector<int>& A, int K) {
        map<int, int> mp;
        mp[0] = 1;
        int sum = 0;
        int cnt = 0;
        for(int i=0;i<A.size();++i){
            sum += A[i];
            sum = ((sum % K) + K ) % K;
            if(mp.find(sum)!=mp.end()){
                cnt += mp[sum];
            }
            ++mp[sum];
        }
        return cnt;
    }
};

时间复杂度：O(n)
空间复杂度：O(min(n, K))
时间复杂度为O(n)出现在K>n时。如K很大，而A中每个元素都很小，且都是正数。例如 A=[1,1,1,1,1,1,1], K = A.size() + 1。