LeetCode 0532. K-diff Pairs in an Array Solution in Java, C++, Python & More | Explanation + Code

Description

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

Solutions

Solution 1: Hash Table

Since k is a fixed value, we can use a hash table ans to record the smaller value of the pairs, which allows us to determine the larger value. Finally, we return the size of ans as the answer.

We traverse the array nums. For the current number x, we use a hash table vis to record all the numbers that have been traversed. If x-k is in vis, we add x-k to ans. If x+k is in vis, we add x to ans. Then, we add x to vis. Continue traversing the array nums until the end.

Finally, we return the size of ans as the answer.

The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the array nums.

PythonJavaC++GoTypeScriptRust

class Solution: def findPairs(self, nums: List[int], k: int) -> int: ans = set() vis = set() for x in nums: if x - k in vis: ans.add(x - k) if x + k in vis: ans.add(x) vis.add(x) return len(ans)(code-box)

class Solution { public int findPairs(int[] nums, int k) { Set<Integer> ans = new HashSet<>(); Set<Integer> vis = new HashSet<>(); for (int x : nums) { if (vis.contains(x - k)) { ans.add(x - k); } if (vis.contains(x + k)) { ans.add(x); } vis.add(x); } return ans.size(); } }(code-box)

class Solution { public: int findPairs(vector<int>& nums, int k) { unordered_set<int> ans, vis; for (int x : nums) { if (vis.count(x - k)) { ans.insert(x - k); } if (vis.count(x + k)) { ans.insert(x); } vis.insert(x); } return ans.size(); } };(code-box)

func findPairs(nums []int, k int) int { ans := make(map[int]struct{}) vis := make(map[int]struct{}) for _, x := range nums { if _, ok := vis[x-k]; ok { ans[x-k] = struct{}{} } if _, ok := vis[x+k]; ok { ans[x] = struct{}{} } vis[x] = struct{}{} } return len(ans) }(code-box)

function findPairs(nums: number[], k: number): number { const ans = new Set<number>(); const vis = new Set<number>(); for (const x of nums) { if (vis.has(x - k)) { ans.add(x - k); } if (vis.has(x + k)) { ans.add(x); } vis.add(x); } return ans.size; }(code-box)

use std::collections::HashSet; impl Solution { pub fn find_pairs(nums: Vec<i32>, k: i32) -> i32 { let mut ans = HashSet::new(); let mut vis = HashSet::new(); for &x in &nums { if vis.contains(&(x - k)) { ans.insert(x - k); } if vis.contains(&(x + k)) { ans.insert(x); } vis.insert(x); } ans.len() as i32 } }(code-box)