leetcode解题: K-diff Pairs in an Array (532)

发表于 | 分类于

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.

Example 1:

1
2
3
4
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.

Example 2:

1
2
3
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).

Example 3:

1
2
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].

解法1：Two pointers, O(NlogN) Time + O(1) Space

可以先排序，这样找距离为k的数就好找了。用Two pointers的方法来解，left负责从左到右遍历，right负责找对应于left的距离为k的数。
这题的坑点在于有重复的值，所以left需要去重，也就是下面程序的i， 那么如果说i在循环内因为重复的问题已经向前进了，那么right进行到下一次循环的时候需要至少从i+1开始，也就是
我们的那句j = Math.max(i + 1, j)的意义。
Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public class Solution {
    public int findPairs(int[] nums, int k) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        
        Arrays.sort(nums); // first sort the input
        
        int res = 0, j = 1;
        int n = nums.length;
        for (int i = 0; i < n - 1; ++i) {
            j = Math.max(i + 1, j);
            while ( j < n && (long)nums[j] - nums[i] < k) {
                ++j;
            }
            if (j < n && (long)nums[j] - nums[i] == k) {
                ++res;
            }
            while (i < n - 1 && nums[i + 1] == nums[i]) {
                ++i;
            }
            
        }
        return res;
    }
}

解法2：HashMap, O(N) Time + O(N) Space

这个解法借用了Two sum的思路，在two sum里，我们用一个hashmap来判断对应的两个数的和是否为target。这里也一样。如果要找寻是否有两个数的差是否为k， 那么我们也可以把他们都放到map中。
所不同的地方就是这里是统计个数。那么如果k是一个正数，我们只需要判断对应的另外一个数是否在map中。如果k为0， 那么要判断现在这个数出现的次数是否大于1.
Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public class Solution {
    public int findPairs(int[] nums, int k) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int num: nums) {
            if (map.containsKey(num)) {
                map.put(num, map.get(num) + 1);
            } else {
                map.put(num, 1);
            }
        }
        
        int res = 0;
        for (Integer key : map.keySet()) {
            if (k == 0 && map.get(key) > 1) {
                ++res;
            } 
            if (k > 0 && map.containsKey(key + k)) {
                ++res;
            }
        }
        return res;
        
    }
}