[leetcode #532] K-diff Pairs in an Array

Problem

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
・ |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 <= 10⁴
・ -10⁷ <= nums[i] <= 10⁷
・ 0 <= k <= 10⁷

Idea

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

위 식을 만족하는 수의 쌍 (K-diff pairs) 개수를 구하라는 문제다. 쌍은 두 수의 묶음이므로 순서는 고려하지 않아도 된다.

이를 푸는 간단한 방법은 map을 이용하는 것이다. 주어진 배열을 탐색하면서 각 값의 빈도를 센다.
이후 map의 key를 하나씩 탐색하면서 i-k인 값이 map에 존재하는지 확인한다. 존재한다면 count를 1씩 올린다.
예외인 경우는 k==0일 경우다. k가 0이라면 두 수가 같은 경우밖에 없으므로 배열에서 같은 수가 두 번 이상 나와야 한다. 빈도가 2 이상이 아닐 경우 count를 올리지 않는다.

Solution

class Solution {
    public int findPairs(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();

        for (int i=0; i < nums.length; i++) {
            map.put(nums[i], map.getOrDefault(nums[i], 0)+1);
        }

        int res = 0;
        for (int i : map.keySet()) {
            if (k == 0 && map.get(i) <= 1) {
                continue;
            }

            if (map.containsKey(i-k)) {    
                res++;
            }
        }

        return res;
    }
}

Reference

https://leetcode.com/problems/k-diff-pairs-in-an-array/