Algorithm
Problem Name: 532. K-diff Pairs in an Array
Problem Link: https://leetcode.com/problems/k-diff-pairs-in-an-array/
Given an array of integers nums and an integer k, return the number of unique k-diff pairs in the array.
A k-diff pair is an integer pair (nums[i], nums[j]), where the following are true:
0 <= i, j < nums.lengthi != jnums[i] - nums[j] == k
Notice that |val| denotes the absolute value of val.
Example 1:
Input: nums = [3,1,4,1,5], k = 2 Output: 2 Explanation: There are two 2-diff pairs in the array, (1, 3) and (3, 5). Although we have two 1s in the input, we should only return the number of unique pairs.
Example 2:
Input: nums = [1,2,3,4,5], k = 1 Output: 4 Explanation: There are four 1-diff pairs in the array, (1, 2), (2, 3), (3, 4) and (4, 5).
Example 3:
Input: nums = [1,3,1,5,4], k = 0 Output: 1 Explanation: There is one 0-diff pair in the array, (1, 1).
Constraints:
1 <= nums.length <= 104-107 <= nums[i] <= 1070 <= k <= 107
Code Examples
#1 Code Example with Javascript Programming
Code -
Javascript Programming
const findPairs = function(nums, k) {
if(k < 0) return 0
let count = 0
const hash = {}
for(let i = 0; i < nums.length; i++) {
hash[nums[i]] = i
}
for(let i = 0; i < nums.length; i++) {
if(hash.hasOwnProperty(nums[i] + k) && hash[nums[i] + k] !== i> {
count++
delete hash[nums[i] + k]
}
}
return count
};
Input
nums = [3,1,4,1,5], k = 2
Output
2
#2 Code Example with Python Programming
Code -
Python Programming
class Solution:
def findPairs(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: int
"""
dic, pair = {}, 0
for num in nums:
if (num-k in dic or num+k in dic) and (not num in dic or (k==0 and dic[num]==1)) and k>=0:
if num-k in dic and k!=0: pair+=1
if num+k in dic: pair+=1
if num in dic: dic[num]+=1; continue
if num in dic: continue
dic[num]=1
return pair
Input
nums = [3,1,4,1,5], k = 2
Output
2
#3 Code Example with C# Programming
Code -
C# Programming
using System.Collections.Generic;
namespace LeetCode
{
public class _0532_KDiffPairsInAnArray
{
public int FindPairs(int[] nums, int k)
{
if (k < 0) return 0;
var counts = new SortedDictionary<int, int>();
foreach (var num in nums)
{
if (!counts.ContainsKey(num))
counts[num] = 1;
else
counts[num]++;
}
var count = 0;
if (k == 0)
foreach (var key in counts.Keys)
{
if (counts[key] > 1) count++;
}
else
foreach (var key in counts.Keys)
if (counts.ContainsKey(key + k)) count++;
return count;
}
}
}
Input
nums = [1,2,3,4,5], k = 1
Output
4