LeetCode（Map)2006. Count Number of Pairs With Absolute Difference K

灰太狼 2023-09-24 16:37 58阅读 0赞

# 1.问题 #

Given an integer array nums and an integer k, return the number of pairs (i, j) where i < j such that |nums\[i\] - nums\[j\]| == k.

The value of |x| is defined as:

x if x >= 0.  
\-x if x < 0.

Example 1:

> Input: nums = \[1,2,2,1\], k = 1  
> Output: 4  
> Explanation: The pairs with an absolute difference of 1 are:

*  \[1,2,2,1\]
 *  \[1,2,2,1\]
 *  \[1,2,2,1\]
 *  \[1,2,2,1\]

Example 2:

> Input: nums = \[1,3\], k = 3  
> Output: 0  
> Explanation: There are no pairs with an absolute difference of 3.

Example 3:

> Input: nums = \[3,2,1,5,4\], k = 2  
> Output: 3  
> Explanation: The pairs with an absolute difference of 2 are:
> 
>  *  \[3,2,1,5,4\]
>  *  \[3,2,1,5,4\]
>  *  \[3,2,1,5,4\]

Constraints:

*  1 <= nums.length <= 200
 *  1 <= nums\[i\] <= 100
 *  1 <= k <= 99

# 2. 解题思路 #

## 方法1： ##

> 1.定义result初始为0  
> 2.for循环，两数相减取绝对值，如果等于k,result基础上加1  
> 3.返回result结果

## 方法2： ##

> 1.新建hashmap，定义result初始为0  
> 2.for循环遍历  
> 1）map中是否有key减去k，说明有和其相减的数值，如果有，map.get(nums\[i\]-k)为1，也就是在result基础上加1  
> 2）map中是否有key加k，说明有和其相减的数值，如果有map.get(nums\[i\]+k)为1，也就是在result基础上加1  
> 3.返回reuslt

## 方法3： ##

> 1.定义长度为101(有1-100的数字）的arr数组，定义count初始为0  
> 2.遍历数组，将nums在i位置上相同个数+1  
> 3.遍历arr数组，arr\[i\]\*arr\[i+k\]是在i位置上出现的重复数字个数和i+k位置上出现的重复数字个数，乘积是两个数字搭配符合要求的个数

# 3. 代码 #

## 代码1： ##

class Solution {
        
        public int countKDifference(int[] nums, int k) {
        
            int result =0;//1.定义result初始为0
            for (int i = 0; i < nums.length; i++) {
        //2.for循环，两数相减取绝对值，如果等于k,result基础上加1
                for(int j=i+1; j<nums.length; j++){
        
                    if(Math.abs(nums[i]-nums[j])==k) result+=1;
                    // if(nums[i]-nums[j]==k) result+=1;
                    // else if( nums[i]-nums[j]==-k) result+=1;
                }
            }
            return result;//3.返回result结果
            
        }
    }

## 代码2： ##

class Solution {
        
        public int countKDifference(int[] nums, int k) {
        
            Map<Integer,Integer> map = new HashMap<>();//1.新建hashmap，定义result初始为0
            int result = 0;
    
            for(int i = 0;i< nums.length;i++){
        //2.for循环遍历
                if(map.containsKey(nums[i]-k)){
        //map中是否有key减去k，说明有和其相减的数值，如果有，map.get(nums[i]-k)为1，也就是在result基础上加1
                    result += map.get(nums[i]-k);
                }
                if(map.containsKey(nums[i]+k)){
        //map中是否有key加k，说明有和其相减的数值，如果有，map.get(nums[i]+k)为1，也就是在result基础上加1
                    result += map.get(nums[i]+k);
                }
                map.put(nums[i],map.getOrDefault(nums[i],0)+1);//map中没有元素，map将数组元素作为key放入map,默认值为0，+1是为reusult加1做铺垫
            }
    
            return result;//3.返回reuslt
            
        }
    }

> 解题思路基本相同

class Solution {
        
        public int countKDifference(int[] nums, int k) {
          
            HashMap<Integer,Integer> hm=new HashMap<>();
            for(int i=0;i<nums.length;i++){
        
                hm.put(nums[i],hm.getOrDefault(nums[i],0)+1);
            }
            int count=0;
            for(int i=0;i<nums.length;i++){
        
                int val=nums[i]+k;
                if(hm.containsKey(val)){
        
                    count+=hm.get(val);
                }
            }
            return count;
        }
    }

class Solution {
        
        public static int countKDifference(int[] nums, int k) {
        
            int counter=0;
            HashMap<Integer,Integer> map= new HashMap<>();
    
            for (int i = 0; i <nums.length ; i++) {
        
                map.put(nums[i],map.getOrDefault(nums[i],0)+1);
            }
            for (int i = 0; i <nums.length ; i++) {
        
                if(map.containsKey(nums[i]-k))
                    counter+=map.get(Math.abs(nums[i]-k));
            }
            return counter;
        }
    }

## 代码3： ##

class Solution {
        
        public int countKDifference(int[] nums, int k) {
        
            int[] arr = new int[101];//1.定义长度为101(有1-100的数字）的arr数组，定义count初始为0
            int count = 0;
            for(int i: nums) {
        //2.遍历数组，将nums在i位置上相同个数+1
                arr[i]++;
            }
            for(int i=0; i+k<101; i++) {
        //3.遍历arr数组，arr[i]*arr[i+k]是在i位置上出现的重复数字个数和i+k位置上出现的重复数字个数，乘积是符合要求的个数
                count += arr[i]*arr[i+k];
            }
            return count;
        }
    }

补充理解：  
![在这里插入图片描述][e797ec6f8f5e4e86913d8af7de504abe.png]

public int countKDifference(int[] nums, int k) {
        
        int n = nums.length;
        int ans =0;
        int [] count = new int [101];
        
        for(int i: nums)
        {
           
            if(i+k<=100)
                ans+= count[i+k];
            
            if(i-k>=1)
                ans+= count[i-k];
    
            count[i]++;
        }
        return ans;
    }

[e797ec6f8f5e4e86913d8af7de504abe.png]: https://img-blog.csdnimg.cn/e797ec6f8f5e4e86913d8af7de504abe.png