// OJ: https://leetcode.com/problems/kdiffpairsinanarray
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(N)
class Solution {
public:
int findPairs(vector<int>& nums, int k) {
if (k < 0) return 0;
unordered_map<int, int> m;
for (int n : nums) m[n]++;
int cnt = 0;
for (auto p : m) {
if ((!k && p.second > 1)
 (k && m.count(p.first + k))) ++cnt;
}
return cnt;
}
};
C++ O(N) Time with unordered_map



Hi @lzl124631x
First of all thanks for the nice solution, however, I think the following code is O(N^2) rather than O(N), since count() in unordered_map is O(N). (http://www.cplusplus.com/reference/unordered_map/unordered_map/count/)for (auto p : m) { if ((!k && p.second > 1)  (k && m.count(p.first + k))) ++cnt; } takes 32ms
Instead of counting the number of key in the map, you can use find() which is O(1) for unordered_map.
for (auto p : m) { if ((!k && p.second > 1)  (k && m.find(p.first + k) != m.end())) ++cnt; } takes 29ms
Thanks.