[Leetcode] 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).

Example 4:

Input: nums = [1,2,4,4,3,3,0,9,2,3], k = 3
Output: 2

Example 5:

Input: nums = [-1,-2,-3], k = 1
Output: 2

Constraints:

• 1 <= nums.length <= 104
• 107 <= nums[i] <= 107
• 0 <= k <= 107

array 안에서 k 의 거리만큼 떨어진 원소가 존재하는지를 찾는 문제이다.

유의 할 점은 같은 쌍의 점은 오직 한번만 카운트 한다는 점이다.

아래는 내가 푼 코드이다.

package leetcode;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

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

        for (int i = 0; i < nums.length; i++) {
            map.merge(nums[i], 1, Integer::sum);
        }

        int count = 0;

        // 같은 점의 연속된 계산을 막기 위해 우선 정렬해준다.
        Arrays.sort(nums);

        for (int i = 0; i< nums.length; i++) {
            map.merge(nums[i], -1, Integer::sum);

            if (map.get(nums[i]) == 0) {
                map.remove(nums[i]);
            }

            // 이미 계산된 시작점이라면 제외해준다.
            if (i != 0 && nums[i-1] == nums[i]) {
                continue;
            }

            if (map.containsKey(nums[i] + k) || map.containsKey(nums[i] - k)) {
                count++;
            }
        }

        return count;
    }

    public static void main(String[] args) {
        int [] nums = {1,2,3,4,5};
        int k = 1;

        KdiffPairsInAnArray kdiffPairsInAnArray = new KdiffPairsInAnArray();

        System.out.println(kdiffPairsInAnArray.findPairs(nums, k));
    }
}

나는 같은 점의 중복 계산을 막기 위해 다소 복잡한 코드를 썼는데,, 사실 이럴 필요가 없었다.

두개의 점이 같은 숫자로 연결되는 경우는 오로지 k=0 인 경우이다.

 

때문에 중복을 모두 지우고 k=0 인 경우만, 예외처리를 해주어도 가능하다.

또한, map 에서 숫자를 그때그때 마다 remove 하는 것도 굳이 안해도 된다.

 

왜냐하면, k=0 인 경우만 예외처리 되었다면, 나머지 경우는 원소들을 지우지 않고 한방향으로 연산(덧셈 혹은 뺄셈) 만 해주게 되면 오로지 하나의 pair 만 얻어올 수 있기 때문이다.

 

예) k=2, 1,3 의 경우 1+2=3 은 카운트 하지만, 3-2=1 은 카운트 하지 않는다.

 

큰 차이는 없지만.. 이렇게 하면 약 4ms 빨라진다.