k-dis数对

[编程题]k-dis数对

热度指数：742 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个长度为 n 的整数数组 nums ，和一个正整数 k，你需要输出不同的 k-dis 数对数量。

k-dis 数对定义为一个整数对 $(nums_i,nums_j) \$ ，满足 $0 \le i < j \le n \$ ，且 $|nums_i-nums_j| = k \$

数据范围： $1 \leq n \leq 10^5 \$ ， $|nums_i| \leq 10^7 \$ ， $0 \leq k \leq 2 * 10^7 \$

示例1

输入

[3,1,4,6,5],3

输出

说明

(4,1),(6,3)

示例2

输入

[3,1,4,6,4],3

输出

说明

(4,1) (6,3) 虽然有两个 (4,1) 数对，但只统计不同的数对

算法知识视频讲解

Java

skwan

使用set进行一次遍历

import java.util.*;


public class Solution {
    public int k_dis(ArrayList<Integer> nums, int k) {
        int n = nums.size();
        int ans = 0;
        Set<Integer> set = new HashSet<>();
        for (int a : nums) set.add(a);
        for (int a : set) {
            if (set.contains( a - k)) ans++;
            if (set.contains( a + k)) ans++;
        }
        return ans / 2;
    }
}

发表于 2022-07-17 16:58:32 回复(1)

Javascript

牛客283687938号

JS，将数组去重排序后所有元素加上K，然后将两个数组合并后去重

function k_dis( nums , k ) {

// write code here
nums = Array.from(new Set(nums))
let numsAddk = nums.map((item)=> item+k)
let len1 = nums.length;
let len2 = numsAddk.length;
let lengthAdd = Array.from(new Set(nums.concat(numsAddk))).length
return len1+len2-lengthAdd;
}
module.exports = {
k_dis : k_dis
};

发表于 2022-09-13 23:47:25 回复(0)