K-diff Pairs in an Array

投稿日 |

Description

Given an array of integers and an integer k, you need to find the number of unique k-diff pairs in the array. Here a k-diff pair is defined as an integer pair (i, j), where i and j are both numbers in the array and their absolute difference is k.

1
2
3
4
5
Example 1:
Input: [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.
1
2
3
4
Example 2:
Input:[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).
1
2
3
4
Example 3:
Input: [1, 3, 1, 5, 4], k = 0
Output: 1
Explanation: There is one 0-diff pair in the array, (1, 1).

Note:

  • The pairs (i, j) and (j, i) count as the same pair.
  • The length of the array won’t exceed 10,000.
  • All the integers in the given input belong to the range: [-1e7, 1e7].

Method

题目中给的是无序的数组然后需要求差值。我们可以先把无序数组进行排序将其变成有序，然后从第一个数开始遍历，通过两个pointer来比较两个数之间的差值。这里要注意的是重复的数字只计算一次，排序之后重复的数字合并到了一起，我们只需要判定第一个pointer前面的数字是否和pointer指向的数字的值相等，若相等则跳过。

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Solution {
    public int findPairs(int[] nums, int k) {
        Arrays.sort(nums);
        int count = 0;
        for(int i = 0; i < nums.length; i++){
            if(i > 0 && nums[i-1] == nums[i]) continue;
            int diff = Integer.MIN_VALUE;
            int j = i + 1;
            while(k > diff && j < nums.length){
                diff = Math.abs(nums[j]-nums[i]);
                j++;
                if(diff == k) count++;
            }
        }
        return count;
    }
}