[LeetCode] 532. K-diff Pairs in an Array

[grandyang]

 

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:

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:

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:

Input: [1, 3, 1, 5, 4], k = 0
Output: 1
Explanation: There is one 0-diff pair in the array, (1, 1).

 

Note:

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

 

这道题给了我们一个含有重复数字的无序数组，还有一个整数k，让找出有多少对不重复的数对 (i, j) 使得i和j的差刚好为k。由于k有可能为0，而只有含有至少两个相同的数字才能形成数对，那么就是说需要统计数组中每个数字的个数。可以建立每个数字和其出现次数之间的映射，然后遍历 HashMap 中的数字，如果k为0且该数字出现的次数大于1，则结果 res 自增1；如果k不为0，且用当前数字加上k后得到的新数字也在数组中存在，则结果 res 自增1，参见代码如下：

 

解法一：

class Solution {
public:
    int findPairs(vector<int>& nums, int k) {
        int res = 0, n = nums.size();
        unordered_map<int, int> m;
        for (int num : nums) ++m[num];
        for (auto a : m) {
            if (k == 0 && a.second > 1) ++res;
            if (k > 0 && m.count(a.first + k)) ++res;
        }
        return res;
    }
};

 

下面这种方法没有使用 HashMap，而是使用了双指针，需要给数组排序，节省了空间的同时牺牲了时间。遍历排序后的数组，然后在当前数字之前找最后一个和当前数之差大于k的数字，若这个数字和当前数字不是同一个位置，且和上一轮 pre 不是同一个数字，且和当前数字之差正好为k，那么结果 res 自增1，然后将 pre 赋值为这个数字，参见代码如下：

 

解法二：

class Solution {
public:
    int findPairs(vector<int>& nums, int k) {
        int res = 0, n = nums.size(), j = 0, pre = INT_MAX;
        sort(nums.begin(), nums.end());
        for (int i = 1; i < n; ++i){           
            while (j < i && nums[i] - nums[j] > k) ++j;
            if (j != i && pre != nums[j] && nums[i] - nums[j] == k) {
                ++res;
                pre = nums[j];
            }
        }
        return res;
    }
};

 

Github 同步地址：

#532

 

类似题目：

Minimum Absolute Difference in BST

 

参考资料：

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

https://leetcode.com/problems/k-diff-pairs-in-an-array/discuss/100104/two-pointer-approach

https://leetcode.com/problems/k-diff-pairs-in-an-array/discuss/100098/Java-O(n)-solution-one-Hashmap-easy-to-understand

 

LeetCode All in One 题目讲解汇总(持续更新中...)