LeetCode（Array) 1512. Number of Good Pairs

柔情只为你懂 2023-09-23 22:54 58阅读 0赞

# 1.问题 #

Given an array of integers nums, return the number of good pairs.

A pair (i, j) is called good if nums\[i\] == nums\[j\] and i < j.

Example 1:

> Input: nums = \[1,2,3,1,1,3\]  
> Output: 4  
> Explanation: There are 4 good pairs (0,3), (0,4), (3,4), (2,5) 0-indexed.

Example 2:

> Input: nums = \[1,1,1,1\]  
> Output: 6  
> Explanation: Each pair in the array are good.

Example 3:

> Input: nums = \[1,2,3\]  
> Output: 0

Constraints:

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

# 2. 解题思路 #

## 方法1： ##

> 1.定义sum的初始值为0  
> 2. 2个for循环遍历数组  
> 3.如果nums\[i\]==nums\[j\]&&i<j，sum的值加1  
> 4.返回sum

## 方法2： ##

> 1.设置data的数组长度为101  
> 2.定义count初始值为0  
> 3.遍历数组，data中出现了多少次nums的数字  
> 4.返回值

## 方法3： ##

> 1.定义count为0,new HashMap  
> 2.遍历数组  
> 3.如果map中有值，取出map的value，在原来出现次数上相加，类似数学上握手的问题n(n-1)/2  
> 4.如果在map中，没有数字，n为key，1为value，意思是在map中只出现一次  
> 5.返回值

# 3. 代码 #

## 代码1： ##

class Solution {
        
        public int numIdenticalPairs(int[] nums) {
        
            int sum = 0; //1.定义sum的初始值为0
            for (int i = 0; i < nums.length; i++) {
        //2.2个for循环遍历数组
                for(int j =i+1; j<nums.length;j++){
        
                    if(nums[i]==nums[j]&&i<j) sum+=1;//3.如果nums[i]==nums[j]&&i<j，sum的值加1
                }
            }
            return sum;//4.返回sum
        }
    }

## 代码2： ##

class Solution {
        
    	public int numIdenticalPairs(int[] nums) {
        
    	    int []data = new int[101] ;//1.设置data的数组长度为101
    	    int count = 0;//2.定义count初始值为0
    	    for (int n: nums)//3.遍历数组，data中出现了多少次nums的数字
    	         data[n]++;
    	   	for (int i = 0; i <= 100; ++i)
                count += data[i] * (data[i] - 1) / 2;//4.for循环遍历数学中的握手问题n(n-1)/2
            return count;
    }

> 和代码2的解题思路基本相同

class Solution {
        
    	public int numIdenticalPairs(int[] nums) {
        
    	    int []data = new int[101] ;//1.设置data的数组长度为101
    	    int count = 0;//2.定义count初始值为0
    	    for (int n: nums)//3.遍历数组，data中出现了多少次nums的数字
    	        count += data[n]++;
    	    return count;//4.返回值
    }

## 代码3 ##

import java.util.HashMap;
    
    class Solution {
        
        public int numIdenticalPairs(int[] nums) {
        
            HashMap<Integer, Integer> map = new HashMap<>();
            int count = 0;//1.定义count为0,new HashMap
            for (int n : nums) {
        //2.遍历数组
                if (map.containsKey(n)) {
        //3.如果map中有值，取出map的value，在原来出现次数上相加，类似数学上握手的问题n(n-1)/2
                    int k = map.get(n);
                    count += k;
                    map.put(n, k + 1);
                } else {
        
                    map.put(n, 1);//4.如果在map中，没有数字，n为key，1为value，意思是在map中只出现一次
                }
            }
            return count;//5.返回值
        }
    }