532. 数组中的 k-diff 数对
题目描述
给定一个整数数组和一个整数 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 <= 104
-107 <= nums[i] <= 107
0 <= k <= 107
答案
我的代码
class Solution { public int findPairs(int[] nums, int k) { int rtn = 0; if (k==0){ Map<Integer,Integer> map = new HashMap<>(); for (int num : nums) { map.put(num,map.getOrDefault(num,0)+1>2?map.getOrDefault(num,0):map.getOrDefault(num,0)+1); } Iterator<Integer> iterator = map.keySet().iterator(); while (iterator.hasNext()){ rtn += map.get(iterator.next())/2; } return rtn; } Set<Integer> set = new TreeSet<>(); for (int num : nums) { set.add(num); } List<Integer> list = new ArrayList<>(set); for (int i = 0; i < list.size()-1; i++) { for (int j = i+1; j < list.size(); j++) { if (Math.abs(list.get(i)-list.get(j))==k){ rtn++; } } } return rtn; } }
官方答案
方法一：哈希表
思路
遍历数组，找出符合条件的数对。因为是寻找不同的数对，所以可以将数对放入哈希表 res，完成去重的效果，最后返回哈希表的长度即可。遍历数组时，可以将遍历到的下标当作潜在的 j，判断 j 左侧是否有满足条件的 i 来构成 k-diff 数对，而这一判断也可以通过提前将下标 jj 左侧的元素都放入另一个哈希表 visited 来降低时间复杂度。如果可以构成，则将数对放入哈希表 res。
代码实现时，由于 k 是定值，知道数对的较小值，也就知道了另一个值，因此我们可以只将数对的较小值放入 res，而不影响结果的正确性。判断完之后，再将当前元素放入 visited，作为后续判断潜在的 nums[i]。
代码
class Solution { public int findPairs(int[] nums, int k) { Set<Integer> visited = new HashSet<Integer>(); Set<Integer> res = new HashSet<Integer>(); for (int num : nums) { if (visited.contains(num - k)) { res.add(num - k); } if (visited.contains(num + k)) { res.add(num); } visited.add(num); } return res.size(); } }
复杂度分析
时间复杂度：O(n)，其中 n 是数组 nums 的长度。需要遍历 nums 一次。
空间复杂度：O(n)，其中 n 是数组 nums 的长度。两个哈希表最多各存放 n 个元素。
方法二：排序 + 双指针
思路
题干的两个条件可以这样解读：
数对的两个元素的下标值不同。当 k=0 时，数对的两个元素值可以相同，但下标值必须不同。
数对的两个元素差值为 k。
这样的解读之下，原来 i 和 j 的大小关系被抹除了，只要求 i 和 j 不相等。而差值为 k 这一要求则可以在排序后使用双指针来满足。
将原数组升序排序，并用新的指针 xx 和 yy 来搜索数对。即寻找不同的 (nums[x],nums[y]) 满足：
x<y
nums[x]+k=nums[y]
记录满足要求的 xx 的个数并返回。
代码
class Solution: def findPairs(self, nums: List[int], k: int) -> int: nums.sort() n, y, res = len(nums), 0, 0 for x in range(n): if x == 0 or nums[x] != nums[x - 1]: while y < n and (nums[y] < nums[x] + k or y <= x): y += 1 if y < n and nums[y] == nums[x] + k: res += 1 return res
复杂度分析
时间复杂度：O(nlogn)，其中 n 是数组 nums 的长度。排序需要消耗 O(nlogn) 复杂度，遍历指针 x 消耗 O(n) 复杂度，指针 y 的值最多变化 O(n) 次，总的时间复杂度为 O(nlogn)。
空间复杂度：O(logn)，其中 n 是数组 nums 的长度。排序消耗 O(logn) 复杂度，其余消耗常数空间复杂度，总的空间复杂度为 O(logn)。
