-
Notifications
You must be signed in to change notification settings - Fork 5
/
LC_532_KdiffPairsinArray.cpp
82 lines (67 loc) · 1.86 KB
/
LC_532_KdiffPairsinArray.cpp
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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
/*
https://leetcode.com/problems/k-diff-pairs-in-an-array/
532. K-diff Pairs in an Array
*/
class Solution {
public:
int findPairs(vector<int>& nums, int k) {
unordered_map<int,int> um;
int count=0;
for(int x: nums)
{
if(um.find(x) != um.end() )
{
if(k>0)
continue; // skip the repeated elements
else if(um[x]==1) // if 1,1,1,1,1
count++;
}
else
{
if(um.find(x+k) != um.end()) count++;
if(um.find(x-k) != um.end()) count++;
}
um[x]++;
}
/*
for(int x: nums)
um[x]++;
if(k==0)
{
for(auto f: um)
{
if(f.second>1)
count++;
}
}
else {
for(auto f: um)
if(um.find(f.first+k) != um.end()) //every ele is present in map
count++;
}
*/
return count;
}
int findPairs__(vector<int>& nums, int k) {
sort(nums.begin(), nums.end());
int i=0, j=1, diff=0; //there is monotonicity that we are moving in only one direction in order to determine the answer.
int count=0, n = nums.size();
while(i<n && j<n)
{
diff = abs(nums[i]-nums[j]);
if(diff > k) {
i++; //decrease the diff
if(i==j) j++;
}
else if(diff < k) j++;
else
{
i++; j++;
// while(i<n && nums[i]==nums[i-1])i++;
while(j<n && nums[j]==nums[j-1])j++;
count++;
}
}
return count;
}
};