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 <= A.length <= 30000
-10000 <= A[i] <= 10000
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; } };
No comments:
Post a Comment