题目

给定一个整数数组和一个整数 k，你需要在数组里找到 不同的 k-diff 数对，并返回不同的 k-diff 数对 的数目。
这里将 k-diff 数对定义为一个整数对 (nums[i], nums[j])，并满足下述全部条件：
0 <= i < j < nums.length|nums[i] - nums[j]| == k注意，|val| 表示 val 的绝对值。
示例 1：
输入：nums = [3, 1, 4, 1, 5], k = 2输出：2解释：数组中有两个 2-diff 数对, (1, 3) 和 (3, 5)。尽管数组中有两个1，但我们只应返回不同的数对的数量。
示例 2：
输入：nums = [1, 2, 3, 4, 5], k = 1输出：4解释：数组中有四个 1-diff 数对, (1, 2), (2, 3), (3, 4) 和 (4, 5)。
示例 3：
输入：nums = [1, 3, 1, 5, 4], k = 0输出：1解释：数组中只有一个 0-diff 数对，(1, 1)。
提示：
1 <= nums.length <= 10^4-107 <= nums[i] <= 10^70 <= k <= 10^7
来源：力扣（LeetCode）链接：https://leetcode.cn/problems/k-diff-pairs-in-an-array著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

类似两数之和问题，比较容易想到的是使用哈希表存储已经遍历过的数，然后遇到新的数num时，查找num-k和num+k是否存在于哈希表。如果存在，将符合条件的数对加入另一个哈希表（这里使用set即可，因为需要去重），可以存储数对中较小的值，最后返回set大小。见代码一。
进一步可以发现，本题不关注数对的先后顺序，因此如果将数组排序，得到的结果也不变。类似「719. 找出第 K 小的数对距离 」，排序后可以使用双指针减少时间复杂度，使用一个指针枚举数对的第一个数，然后移动第二个指针找到数对的第二个数。对于有序数组，两个指针都只需要遍历一次数组。见代码二。

代码

代码一 哈希表

class Solution {
public int findPairs(int[] nums, int k) {
// 存储遍历过的数
Set visited = new HashSet();
// 存储符合条件的数对中较小的值
Set left = new HashSet();
for (int num : nums) {
if (visited.contains(num - k)) {
left.add(num - k);
}
if (visited.contains(num + k)) {
left.add(num);
}
visited.add(num);
}
return left.size();
}
}

代码二 排序+双指针

class Solution {
public int findPairs(int[] nums, int k) {
Arrays.sort(nums);
int ans = 0;
int n = nums.length;
for (int i = 0, j = 0; i < n; i++) {
// 只关注相同的数中第一次出现的那个，将其作为数对的左端点
if (i == 0 || nums[i] != nums[i - 1]) {
// j不能落后于i，而k为0时，不会进入while循环，就会使j落后于i，为了避免这种情况，可以循环前将j移动到i后一位
j = i + 1;
while (j < n && nums[j] < nums[i] + k) {
j++;
}
if (j < n && nums[j] == nums[i] + k) {
ans++;
}
}
}
return ans;
}
}