K_pairs

题目说明

英文题目：
Given an array of integers and an integer k, you need to find the number of unique k-diff pairs in the array. Here a k-diff pair is defined as an integer pair (i, j), where i and j are both numbers in the array and their absolute difference is k.
中文题目（自己翻译）：
给定一个整数k和整数组，在数组中找出所有的两个数相减的值为k的个数，要求（x,y）和（y,x）属于一个，只能计算一次。

例如1：

输入： [ 3,1,4,1,5 ]，k = 2
输出： 2
说明：数组中有两对满足，即（1,3）和（3,5）。
虽然我们在输入中有两个1，但我们应该只返回唯一对的数量。

例如2：

输入： [ 1,2,3,4,5 ]，k = 1
输出： 4
说明：在阵列中有四对，（1,2），（2,3），（3,4）和（4,5）。

例如3：

输入： [ 1,3,1,5,4 ]，k = 0
输出： 1
说明：数组中有一对，（1,1）。

解题思路

首先，需要注意：

（1）（x,y）和（y,x）是相同的；  
（2）k为负数的时候，返回0；k为正数的时候分情况；

当k为正数的时候，又分为k=0和k!=0 的情况。
k != 0的情况：

（1）排序；
（2）去重；
（3）数组内两两相减，判断是否等于k,相等则计数器+1;

k = 0的情况：

（1）排序；
（2）去重，去重的时候需要注意，不是讲所有的重复的值去掉，是将两个或两个以上的重复的值去掉之后变成只有两个重复的值；
（3）数组内两两相减，判断是否等于k,相等则计数器+1;

这两种情况下的去重的格式是不一样的。

代码

有了上述的解题思路之后，需要考虑到时间复杂度和空间复杂度的。

方法一，时间复杂度O(n^2):

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var findPairs = function(nums, k) {
    
    // 判断k是否小于0或者数组的长度是否为0，是则返回0。
    if(nums.length === 0 || k<0) return 0;
    
    // 将数组从小到大排序
     nums.sort((x,y) => {return x-y;})
    
     // 两种情况下的去重
     if(k !== 0) {
         let setArr = new Set(nums);
         nums = [...setArr];
         // console.log(nums)
     }else{
         for(let i = 2; i<nums.length;i++ ){
             if(nums[i-2] === nums[i]) {
                 nums.splice(i,1);
                 i--;
             }
         }
     }
    
     let length = nums.length;
     let count = 0;

    // 数组内两两相减，判断是否等于k,相等则计数器count+1
     for(let i = 0; i<length-1; i++) {
         for(let j = i+1 ;j<length ;j++) {
             let D_value = (nums[j] - nums[i]);
             if(D_value === k) {
                 count++;
                 break;
             }
         }
     }
    
     return count;
};

方法二，时间复杂度O(n):

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var findPairs = function(nums, k) {
    
    // 判断k是否小于0或者数组的长度是否为0，是则返回0。
    if(nums.length === 0 || k<0) return 0;

    if(k !== 0) {
        // 去重，记录下去重之后的长度。
        let setArr = new Set(nums);
        let size = setArr.size;
        nums = [...setArr];
        
        // 转化成数组之后加上k,并将其添加到setArr里边；
        for(let i = 0 ;i<size;i++) {
            // nums[i] += k;
            setArr.add(nums[i]+k);
        }
        
        // 返回满足题目的对数，size*2表示没有重复时setArr的长度，减去setArr的长度，就是重复的个数，也就是我们要的值。
        return (size*2 - setArr.size);
    }else{
        // 排序
        nums.sort((x,y) => {return x-y;});
        
        // 将两个或两个以上的重复的值变成两个
        for(let i = 2; i<nums.length;i++ ){
            if(nums[i-2] === nums[i]) {
                nums.splice(i,1);
                i--;
            }
        }
        
        // 去重之后计算长度，用数组长度减去去重之后的长度，就表示k个重复的值。
        let size = (new Set(nums)).size;
        
        return nums.length-size;
    }
};

结论

本题主要需要考虑到k大于0 和等于0的情况，因为在两种情况下所使用的去重方法不同；

其次，就是在等于0 的时候所用的去重方法，不是将所有的都去掉，而是要将两个以上的保留成两个。