class Solution:
def findPairs(self, nums: List[int], k: int) -> int:
"""
to avoid duplicate, use map to record the occurance of each unique number.
case1: k > 0 instead of loop through each unique number to check match for current number, use map to directly check if cur_num + k in the dictionary at O(1) time
Case2: k=0, it can be converted to find another number same as itself. In order to avoid duplicate, just check if there is a number whose occurance is bigger than 0.
"""
# time O(N) space O(N)
res = 0
cnt = collections.Counter(nums)
# step2: loop each unique number: case1=> k >0: check if key +k exist in cnt case 2=> k == 0, check if cnt value > 1
for num in cnt:
if k > 0 and num + k in cnt:
res += 1
if k == 0 and cnt[num] > 1:
res += 1
return res
solution 2: two pointers
class Solution:
def findPairs(self, nums: List[int], k: int) -> int:
# time O(NlgN) ~ O(N^2) space O(1)
if k < 0 or len(nums) < 2:
return 0
res,size = 0, len(nums)
nums.sort()
l,r = 0 ,1
while r < size :
nl,nr = nums[l],nums[r]
# if diff < k : move right ptr
if nr- nl <k:
r += 1
# if dff > k : move left ptr
elif nr - nl > k:
l += 1
else:
# if equal, move l, r to next different number
res += 1
while l < size and l + 1 < size and nums[l] == nl:
l += 1
while r < size and r + 1 < size and nums[r] == nr:
r += 1
# left and right should not be same number
if l == r:
r += 1
return res