974. Subarray Sums Divisible by K ---------M~~~~~~~

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

 

Example 1:

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]

 

Note:

1. 1 <= A.length <= 30000
2. -10000 <= A[i] <= 10000
3. 2 <= K <= 10000

 

A:

这是我Facebook phone interview的题目， 然后，之前没有做过。 估计挂了。（给出的是用map, 和visitedSet。 而没有 做 %k  操作。 哎，还是水平不行啊， Tiger

class Solution {
public:
    int subarraysDivByK(vector<int>& A, int K) {
        int total = 0;
        vector<int> Count(K,0);// use index as count
        Count[0]=1;
        for(auto val : A){
            val %= K;
            total = (K + total+val)%K;// make all them to be positive
            Count[total]++;
        }
        int res = 0;
        for(int i =0;i<K;i++){
            res += Count[i] * (Count[i]-1)/2; // to itself
        }
        return res;
    }
};

网上的答案， 异曲同工，然而不需要考虑 % 后的正负问题。

class Solution {
public:
    int subarraysDivByK(vector<int>& v, int k) {
        
        map<int,int> mp;
        
        int ans=0,r=0;
        for(int i=0;i<v.size();i++){
            r=(r+v[i])%k;
            if(r==0)ans++; //subarray starting from index zero
            ans+=mp[(r+k)%k]; //(r+k)%k is used to deal with negative r as array contains negative numbers also.
            mp[(r+k)%k]++;
        }
        
        return ans;
    }
};