中等

问题描述

给定一个整数数组和一个整数 k，你需要在数组里找到 不同的 k-diff 数对，并返回不同的 k-diff 数对 的数目。

这里将 k-diff 数对定义为一个整数对 (nums[i], nums[j])，并满足下述全部条件：

• 0 <= i, j < nums.length
• i != j
• |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

哈希表

建立两个集合 $vis$ 和 $ans$，$vis$ 用于存放遍历过的数字，$ans$ 用于存放答案值，由于 $k$ 是定值，只要确定其中一个值，另外一个值也就确定了，所以，答案集合只记录数对中较小的值或较大的值，就能达到去重的目的。遍历数组，设当前是遍历到的数字为 $num$，如果 $vis$ 中存在 $num + k$，说明存在数对 $[num, num + k]$ 满足要求，将 $num$ 放入答案集中；如果 $vis$ 中存在 $num - k$，说明存在数对 $[num - k, num]$ 满足要求，将 $num - k$ 放入答案集中，最终返回答案集 $ans$ 的大小。

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var findPairs = function (nums, k) {
  const vis = new Set()
  const ans = new Set()
  for (const num of nums) {
    if (vis.has(num + k)) {
      ans.add(num)
    }
    if (vis.has(num - k)) {
      ans.add(num - k)
    }
    vis.add(num)
  }
  return ans.size
}

• 时间复杂度：$O(n)$，需要遍历一次数组。
• 空间复杂度：$O(n)$，需要创建两个集合。

二分查找

首先对原数组进行排序，然后遍历数组，假设当前遍历到第 $i$ 个数为 $num$，那么在第 $i + 1$ 到 $n - 1$ 范围中使用二分查找，确定是否存在 $num + k$ 的数，如果存在，则结果数加一，为了减少重复的计算，当存在 $nums[i] === nums[i-1]$ 时，可以直接跳过，因为 $nums[i]$ 已经在上一轮查找过了，同时因为是用小的数找大的数，也不存在重复统计的情况。

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var findPairs = function (nums, k) {
  nums.sort((a, b) => a - b)
  const n = nums.length
  const find = (l, r, x) => {
    while (l <= r) {
      const mid = ((r - l) >> 1) + l
      if (nums[mid] === x) return true
      else if (nums[mid] > x) r = mid - 1
      else l = mid + 1
    }
    return false
  }
  let ans = 0
  for (let i = 0; i < n; i++) {
    while (i > 0 && nums[i] === nums[i - 1]) i++
    if (find(i + 1, n - 1, nums[i] + k)) {
      ans++
    }
  }
  return ans
}

• 时间复杂度：$O(n\times log\,n)$，排序时间复杂度为$O(n\times log\,n)$，$n$ 次二分查找所需的时间复杂度为$O(n\times log\;n)$
• 空间复杂度：$O(log\,n)$，排序空间复杂度为$O(log\,n)$，其余为常数空间复杂度。