[LeetCode] K-diff Pairs in an Array 数组中差为K的数对

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，而只有含有至少两个相同的数字才能形成数对，那么就是说我们需要统计数组中每个数字的个数。我们可以建立每个数字和其出现次数之间的映射，然后遍历哈希表中的数字，如果k为0且该数字出现的次数大于1，则结果res自增1；如果k不为0，且用当前数字加上k后得到的新数字也在数组中存在，则结果res自增1，参见代码如下：

解法一：

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;
    }
};

下面这种方法没有使用哈希表，而是使用了双指针，需要给数组排序，节省了空间的同时牺牲了时间。我们遍历排序后的数组，然后在当前数字之后找第一个和当前数之差不小于k的数字，若这个数字和当前数字之差正好为k，那么结果res自增1，然后遍历后面的数字去掉重复数字，参见代码如下： 

解法二：

public:
    int findPairs(vector<int>& nums, int k) {
        int res = 0, n = nums.size(), j = 0;
        sort(nums.begin(), nums.end());
        for (int i = 0; i < n; ++i) {
            int j = max(j, i + 1);
            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] == nums[i + 1]) ++i;
        }
        return res;
    }
};

 本文转自博客园Grandyang的博客，原文链接：K-diff Pairs in an Array 数组中差为K的数对，如需转载请自行联系原博主。