class Solution {
public:
int findPairs(vector<int>& nums, int k) {
}
};
532. 数组中的 k-diff 数对
给你一个整数数组 nums 和一个整数 k，请你在数组中找出 不同的 k-diff 数对，并返回不同的 k-diff 数对 的数目。
k-diff 数对定义为一个整数对 (nums[i], nums[j]) ，并满足下述全部条件：
0 <= i, j < nums.lengthi != jnums[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] <= 1070 <= k <= 107相似题目
原站题解
python3 解法, 执行用时: 56 ms, 内存消耗: 16.1 MB, 提交时间: 2023-01-04 10:31:14
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
golang 解法, 执行用时: 8 ms, 内存消耗: 3.7 MB, 提交时间: 2023-01-04 10:30:53
// 排序 + 双指针
func findPairs(nums []int, k int) (ans int) {
sort.Ints(nums)
y, n := 0, len(nums)
for x, num := range nums {
if x == 0 || num != nums[x-1] {
for y < n && (nums[y] < num+k || y <= x) {
y++
}
if y < n && nums[y] == num+k {
ans++
}
}
}
return
}
javascript 解法, 执行用时: 92 ms, 内存消耗: 43 MB, 提交时间: 2023-01-04 10:30:28
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var findPairs = function(nums, k) {
nums.sort((a, b) => a - b);
let n = nums.length, y = 0, res = 0;
for (let x = 0; x < n; x++) {
if (x === 0 || nums[x] !== nums[x - 1]) {
while (y < n && (nums[y] < nums[x] + k || y <= x)) {
y++;
}
if (y < n && nums[y] === nums[x] + k) {
res++;
}
}
}
return res;
};
java 解法, 执行用时: 4 ms, 内存消耗: 40.9 MB, 提交时间: 2023-01-04 10:30:14
class Solution {
public int findPairs(int[] nums, int k) {
Arrays.sort(nums);
int n = nums.length, y = 0, res = 0;
for (int x = 0; x < n; x++) {
if (x == 0 || nums[x] != nums[x - 1]) {
while (y < n && (nums[y] < nums[x] + k || y <= x)) {
y++;
}
if (y < n && nums[y] == nums[x] + k) {
res++;
}
}
}
return res;
}
}
java 解法, 执行用时: 8 ms, 内存消耗: 42 MB, 提交时间: 2023-01-04 10:29:59
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();
}
}
javascript 解法, 执行用时: 64 ms, 内存消耗: 45.3 MB, 提交时间: 2023-01-04 10:29:45
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var findPairs = function(nums, k) {
const visited = new Set();
const res = new Set();
for (const num of nums) {
if (visited.has(num - k)) {
res.add(num - k);
}
if (visited.has(num + k)) {
res.add(num);
}
visited.add(num);
}
return res.size;
};
golang 解法, 执行用时: 12 ms, 内存消耗: 6.1 MB, 提交时间: 2023-01-04 10:29:32
func findPairs(nums []int, k int) int {
visited := map[int]struct{}{}
res := map[int]struct{}{}
for _, num := range nums {
if _, ok := visited[num-k]; ok {
res[num-k] = struct{}{}
}
if _, ok := visited[num+k]; ok {
res[num] = struct{}{}
}
visited[num] = struct{}{}
}
return len(res)
}
python3 解法, 执行用时: 40 ms, 内存消耗: 17 MB, 提交时间: 2023-01-04 10:29:16
class Solution:
def findPairs(self, nums: List[int], k: int) -> int:
visited, res = set(), set()
for num in nums:
if num - k in visited:
res.add(num - k)
if num + k in visited:
res.add(num)
visited.add(num)
return len(res)