532. K-diff Pairs in an Array

leetcode medium

#array#csharp#hash-table#leetcode#medium#search

Task

Дан массив целых чисел nums и целое число k. Верните количество уникальных пар с разницей k в массиве.

Пара с разницей k — это пара целых чисел (nums[i], nums[j]), для которой выполняются следующие условия:

0 <= i, j < nums.length

i != j

|nums[i] - nums[j]| == k

Обратите внимание, что |val| обозначает абсолютное значение val.

Пример:

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.

C# solution

matched/original

public class Solution {
    public int FindPairs(int[] nums, int k) {
        var counter = new Dictionary<int, int>();
        foreach (int num in nums) {
            if (!counter.ContainsKey(num)) {
                counter[num] = 0;
            }
            counter[num]++;
        }
        
        int result = 0;
        foreach (var entry in counter) {
            int x = entry.Key;
            int val = entry.Value;
            if (k > 0 && counter.ContainsKey(x + k)) {
                result++;
            } else if (k == 0 && val > 1) {
                result++;
            }
        }
        
        return result;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int FindPairs(vector<int>& nums, int k) {
        var counter = new unordered_map<int, int>();
        foreach (int num in nums) {
            if (!counter.count(num)) {
                counter[num] = 0;
            }
            counter[num]++;
        }
        
        int result = 0;
        foreach (var entry in counter) {
            int x = entry.Key;
            int val = entry.Value;
            if (k > 0 && counter.count(x + k)) {
                result++;
            } else if (k == 0 && val > 1) {
                result++;
            }
        }
        
        return result;
    }
}

Java solution

matched/original

public class Solution {
    public int findPairs(int[] nums, int k) {

        int result = 0;

        HashMap <Integer,Integer> counter = new HashMap<>();
        for (int n: nums) {
            counter.put(n, counter.getOrDefault(n, 0)+1);
        }

        for (Map.Entry <Integer, Integer> entry: counter.entrySet()) {
            int x = entry.getKey();
            int val = entry.getValue();
            if (k > 0 && counter.containsKey(x + k)) {
                result++;
            } else if (k == 0 && val > 1) {
                result++;
            }
        }
        return result;
    }
}

JavaScript solution

matched/original

var findPairs = function(nums, k) {
    let counter = new Map();
    for (let num of nums) {
        counter.set(num, (counter.get(num) || 0) + 1);
    }
    
    let result = 0;
    for (let [x, val] of counter) {
        if (k > 0 && counter.has(x + k)) {
            result++;
        } else if (k == 0 && val > 1) {
            result++;
        }
    }
    
    return result;
};

Python solution

matched/original

class Solution:
    def findPairs(self, nums: List[int], k: int) -> int:
        counter = collections.Counter(nums)
        result = 0
        
        for x in counter:
            if k > 0 and (x + k) in counter:
                result += 1
            elif k == 0 and counter[x] > 1:
                result += 1
        
        return result

Go solution

matched/original

func findPairs(nums []int, k int) int {
    counter := make(map[int]int)
    for _, num := range nums {
        counter[num]++
    }
    
    result := 0
    for x, val := range counter {
        if k > 0 {
            if _, exists := counter[x + k]; exists {
                result++
            }
        } else if k == 0 && val > 1 {
            result++
        }
    }
    
    return result
}

Explanation

Algorithm

Создайте частотный хэш-словарь для подсчета количества каждого уникального числа в массиве nums.

Для каждого ключа в хэш-словаре проверьте, можно ли найти пару, удовлетворяющую условиям:

Если k > 0, проверьте, существует ли ключ, равный x + k.

Если k == 0, проверьте, есть ли более одного вхождения x.

Увеличьте счётчик результатов, если условие выполняется.

😎