Algorithm


Problem Name: 532. 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.length
  • i != j
  • nums[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] <= 107
  • 0 <= 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
};
Copy The Code & Try With Live Editor

Input

x
+
cmd
nums = [3,1,4,1,5], k = 2

Output

x
+
cmd
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
Copy The Code & Try With Live Editor

Input

x
+
cmd
nums = [3,1,4,1,5], k = 2

Output

x
+
cmd
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;
        }
    }
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
nums = [1,2,3,4,5], k = 1

Output

x
+
cmd
4
Advertisements

Demonstration


Previous
#530 Leetcode Minimum Absolute Difference in BST Solution in C, C++, Java, JavaScript, Python, C# Leetcode
Next
#535 Leetcode Encode and Decode TinyURL Solution in C, C++, Java, JavaScript, Python, C# Leetcode