974. Subarray Sums Divisible by K解题报告

Description:

image.png

Link:

https://leetcode.com/problems/subarray-sums-divisible-by-k/

解题方法：

If Sum[0 to i] % K == Sum[0 to j] and i < j, then Sum[i + 1 to j] % K == 0, so each time we find out an existing mod result, it means we find out a sub-array which sum of this sub-array is divisible by K. Then we can use a hash map to save the count of each mod result. But how can we get the total count of this kinda sub-arrays? For example:
We have a mod result 4 has been happened a bunch of time.
Let's say, we got mod result 4 at index i, j , k, l:
At second time we got 4 at j, which mean, the subarray[i + 1, j] is what we are looking for.
At third time we got 4 at k, subarray[j + 1, k] is what we are looking for, but subarray[i + 1, k] is also the subarray with sum is divisible by K. So at this point we actually find out hash[4] - 1 subarrays.

Tips:

C++ allows a % b and a < 0, but python not.

Time Complexity：

O(n)

完整代码：

class Solution {
public:
    int subarraysDivByK(vector<int>& A, int K) {
        if(!K || A.size() == 0)
            return 0;
        unordered_map<int, int> hash;
        hash[0] = 1;
        int mod = 0, ans = 0, sum = 0;
        for(int i = 0; i < A.size(); i++) {
            sum += A[i];
            while(sum < 0)
                sum += K;
            mod = sum % K;
            if(hash.find(mod) != hash.end()) {
                ans += hash[mod];
            }
            hash[mod]++;
        }
        return ans;
    }
};