顺利遍历、排序双指针、哈希集合，求解《532. 数组中的 k-diff 数对》
例题
532. 数组中的 k-diff 数对
给你一个整数数组 nums 和一个整数 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 ，但我们只应返回不同的数对的数量。
答案
顺利遍历 · 暴力算法
var findPairs = function(nums, k) {
const n = nums.length, s = new Set
for (let i = 0; i < n; i++) {
for (let j = i + 1; j < n; j++) {
if (Math.abs(nums[i] - nums[j]) === k) {
let key = ''
if (nums[i] > nums[j]) key = nums[i] * 10 + nums[j]
else key = nums[j] * 10 + nums[i]
s.add(key)
}
}
}
return s.size
};排序 · 双指针
var findPairs = function(nums, k) {
const n = nums.length
nums.sort((a, b) => a - b)
let j = r = 0
for (let i = 0; i < n; i++) {
if (i > 0 && nums[i] === nums[i - 1]) continue
while (j < n && (nums[j] < nums[i] + k || j === i)) j++
if (j < n && nums[j] === nums[i] + k) r++
}
return r
};function findPairs(nums: number[], k: number): number {
const n = nums.length
nums.sort((a, b) => a - b)
let r = 0
for (let i = 0, j = 0; i < n; i++) {
if (i > 0 && nums[i - 1] === nums[i]) continue
while (j < n && (i === j || nums[j] < nums[i] + k)) j++
if (j < n && nums[j] === nums[i] + k) r++
}
return r
};func findPairs(nums []int, k int) int {
n, r := len(nums), 0
sort.Ints(nums)
for i, j := 0, 0; i < n; i++ {
if i > 0 && nums[i] == nums[i - 1] {
continue
}
for j < n && (nums[j] < nums[i] + k || i == j) {
j++
}
if j < n && nums[j] == nums[i] + k {
r++
}
}
return r
}class Solution {
function findPairs($nums, $k) {
$n = count($nums);
$r = 0;
$j = 0;
sort($nums);
for ($i = 0; $i < $n; $i++) {
if ($i > 0 && $nums[$i] === $nums[$i - 1]) continue;
while ($j < $n && ($i === $j || $nums[$j] < $nums[$i] + $k)) $j++;
if ($j < $n && $nums[$j] === $nums[$i] + $k) $r++;
}
return $r;
}
}class Solution {
public int findPairs(int[] nums, int k) {
int n = nums.length, r = 0;
Arrays.sort(nums);
for (int i = 0, j = 0; i < n; i++) {
if (i > 0 && nums[i] == nums[i - 1]) continue;
while (j < n && (i == j || nums[j] < nums[i] + k)) j++;
if (j < n && nums[j] == nums[i] + k) r++;
}
return r;
}
}class Solution:
def findPairs(self, nums: List[int], k: int) -> int:
n, r, j = len(nums), 0, 0
nums.sort()
for i in range(0, n):
if i > 0 and nums[i] == nums[i - 1]: continue
while j < n and (i == j or nums[j] < nums[i] + k): j += 1
if j < n and nums[j] == nums[i] + k: r += 1
return r哈希集合
var findPairs = function(nums, k) {
const visited = new Set(), r = new Set(), n = nums.length
for (let i = 0; i < n; i++) {
if (visited.has(nums[i] - k)) r.add(nums[i] - k)
if (visited.has(nums[i] + k)) r.add(nums[i])
visited.add(nums[i])
}
return r.size
};function findPairs(nums: number[], k: number): number {
const n = nums.length, visited = new Set(), r = new Set()
for (let i = 0; i < n; i++) {
if (visited.has(nums[i] - k)) r.add(nums[i] - k)
if (visited.has(nums[i] + k)) r.add(nums[i])
visited.add(nums[i])
}
return r.size
};func findPairs(nums []int, k int) int {
type void struct{}
var value void
visited, r := make(map[int]void), make(map[int]void)
for _, num := range nums {
if _, ok := visited[num - k]; ok {
r[num - k] = value
}
if _, ok := visited[num + k]; ok {
r[num] = value
}
visited[num] = value
}
return len(r)
}class Solution {
function findPairs($nums, $k) {
$visited = array();
$r = array();
foreach ($nums as $num) {
if ($visited[$num - $k] !== null) $r[$num - $k] = 1;
if ($visited[$num + $k] !== null) $r[$num] = 1;
$visited[$num] = 1;
}
return count(array_filter($r));
}
}class Solution {
public int findPairs(int[] nums, int k) {
Set<Integer> visited = new HashSet<Integer>();
Set<Integer> r = new HashSet<Integer>();
for (int num : nums) {
if (visited.contains(num - k)) r.add(num - k);
if (visited.contains(num + k)) r.add(num);
visited.add(num);
}
return r.size();
}
}class Solution:
def findPairs(self, nums: List[int], k: int) -> int:
visited, r = set(), set()
for num in nums:
if num - k in visited: r.add(num - k)
if num + k in visited: r.add(num)
visited.add(num)
return len(r)