Description:
https://leetcode.com/problems/k-diff-pairs-in-an-array/description
Code:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
class Solution { public: int findPairs(vector<int>& nums, int k) { if (nums.size() == 0) return 0; if (k < 0) return 0; int result = 0; if (k == 0) { sort(nums.begin(), nums.end()); int switcher = 0; for (int i = 0; i < nums.size() - 1; i++) { if (nums[i + 1] == nums[i]) { if (switcher == 0) { result++; switcher = 1; } } else { switcher = 0; } } } else { unordered_map< int, int> mapping; sort(nums.begin(), nums.end()); nums.erase(unique(nums.begin(), nums.end()), nums.end()); for (int i = 0; i < nums.size(); ++i) { mapping[nums[i]] = i; } for (int i = 0; i < nums.size(); ++i) { int target = nums[i] + k; if (mapping.find(target) != mapping.end()) result++; } } return result; } }; |
Time & Space:
O(nlog(n)) & O(n)
The O(N) version:
class Solution {
public:
int findPairs(vector& nums, int k) {
if (k < 0) return 0;
unordered_set res, vd;
for (const int x : nums) {
if (vd.count(x – k)) {
res.insert(x – k);
}
if (vd.count(x + k)) {
res.insert(x);
}
vd.insert(x);
}
return res.size();
}
};