题目描述

给你一个整数数组 nums 。

如果一组数字 (i,j) 满足 nums[i] == nums[j] 且 i < j ，就可以认为这是一组 好数对 。

返回好数对的数目。

链接：https://leetcode-cn.com/problems/number-of-good-pairs/

解题思路

拿到这个题的一个想法感觉这是一个数学题，从n个数里找到2个相同元素的个数，是排列组合问题也就是C(n, 2)

可以知道的是，对于排列有公式：

对于组合有公式：

因为我们要找的是2个元素的组合，所以我们把2带入公式得到：

C(n, 2)

= n! / 2! (n - 2)!

= n * n - 1 * n - 2 … * 1 / 2 * n - 2 * n - 3 … * 1

= n * n - 1 / 2

所以最后使用这个公式即可计算出结果

• 这里我使用一个map存储同一个数字出现的次数
• 再计算这个数字的组合数
• 最后将所有的组合数相加

Code

func numIdenticalPairs(nums []int) int {
	res := 0
	temp := map[int] int {}
	for _, item := range nums {
		temp[item]++
	}
	for _, v := range temp {
		res += (v - 1) * v / 2
	}
	return res
}