Sponsored
Sponsored
This approach uses a HashMap to track the frequency of each element in the array. For each unique element, we will check if there's another element that can form a k-diff pair with it. When k is zero, we need to check if there are duplicates present in the list.
Time Complexity: O(n) because we iterate over the array and then over the hashmap that is bounded by a constant size. Space Complexity: O(n) to store the frequency map.
1#include <unordered_map>
2#include <vector>
3
4int findPairs(std::vector<int>& nums, int k) {
5 std::unordered_map<int, int> freq_map;
6 int count = 0;
7 for (int num : nums) {
8 freq_map[num]++;
9 }
10 for (const auto& pair : freq_map) {
11 if (k == 0) {
12 if (pair.second > 1) count++;
13 } else if (freq_map.find(pair.first + k) != freq_map.end()) {
14 count++;
15 }
16 }
17 return count;
18}Using a C++ unordered_map as a frequency map, it calculates all possible k-diff pairs by iterating through the map. For k differences of zero, the pair's value must occur more than once.
This approach involves sorting the array initially, then using two pointers to determine unique k-diff pairs. The array being sorted helps us efficiently reduce potential pair checks, and ensure pairs are considered only once.
Time Complexity: O(n log n) due to sorting. Space Complexity: O(1) if disregard input.
1#
After sorting, two pointers start from the beginning. We adjust pointers depending on the difference relative to k. Duplicates are handled by skipping same values.