题目描述

https://leetcode.com/problems/number-of-good-pairs/

Given an array of integers nums.

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

Return the number of good pairs.

 

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

博主第一次提交的代码

博主脑子也不太灵活，直观的思考就是使用排列组合的方式，假如数字7有n个重复的，那么n从中取出任意2个无序的组合可能的种类就是

排列组合公式

代码写出来了，但是提交后值算错了，原来是在factorial函数中，result*=i这一步整形溢出了

class Solution {
    public int numIdenticalPairs(int[] nums) {
        Map<Integer,Integer> cache = new HashMap<>();
        for(int eachInt: nums){
            if(cache.get(eachInt) == null){
                int count = 1;
                cache.put(eachInt,count);
            }else{
                int count = cache.get(eachInt);
                cache.put(eachInt,++count);
            }
        }
        int result = 0;
        for(int eachValue:cache.values()){
            if( eachValue > 1){
                result += factorial(eachValue)/(2* factorial(eachValue-2));
            }
        }
        return result;
    }
    public int factorial(int n){
        if( n == 0){
            return 1;
        }
        int result = 1;
        for(int i=1; i<=n; i++){
            result*=i;
        }
        return result;
    }
}

修复一下整形溢出的问题，把阶乘公式改成long类型，修复完之后依然溢出，那么就得看看别人优秀的解法了

public static long factorial(int n){
        if( n == 0){
            return 1;
        }
        long result = 1;
        for(int i=1; i<=n; i++){
            result*=i;
        }
        return result;
    }

他人优秀的代码

解法一

这个解法也是基于排列组合公式的一个等价公式，并且这段代码避免了重复的乘法，也就不会产生一个值特别大的数字，不会产生整形溢出的问题

排列组合公式

public int numIdenticalPairs(int[] A) {
        int res = 0, count[] = new int[101];
        for (int a: A) {
            res += count[a]++;
        }
        return res;
    }