// 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.

@swimmorning Hi there. unordered_map is basically a hash table and it doesn't allow duplicates, so the number (or counts) of elements with a specified key is either 1 or 0. As the link you provided suggests, the average time complexity is surely O(1), or constant. 'Linear in the number of elements counted' amounts to 'linear in 1 or 0'. What do you think? :)

@Rayarrow Yeah, and cppreference.com says it directly.
Btw,
count
is not only nicer but maybe also faster (I remember having seen that a while ago).

Ok I just tested it again, adding this before the
return
:for (int i=0; i<100000000; i++) //m.count(42); m.find(42) != m.end();
I used "Run Code" three times on the small provided custom input. With
m.count(42);
it took 1516, 1542 and 1529 ms. Withm.find(42) != m.end();
it took 1883, 1869 and 1845 ms.

@ManuelP Wow! I also take it as my cheat sheet as its layout seems more comfortable to me.
Thanks for your "Btw" and tests. So kind of you. I've never delved into the difference of the two methods. As for an unordered_set (or map), I merely tookcount()
andfind()
as two different ways to express my intention in different scenes. What a waste:(