Array 1512 好数对的数目

给你一个整数数组 nums 。

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

返回好数对的数目。

思路

依次遍历（j<i）,找重复数，就可以枚举所有的好数对。

public int numIdenticalPairs(int[] nums) {
    int count = 0;
    for(int i = 0;i<nums.length;i++){
        for(int j = 0;j<i;j++){
            if(nums[i]==nums[j]) {
            	count ++;
            }
        }
    }
    return count;
}

时间复杂度：$O(n^2)$,双重for循环

空间复杂度：只需要存储常数的空间。

方法二：组合计数

假设 k 重复了 v 次，那么满足题目要求的数目为：$\frac{v(v-1)}{2}$，因此我们需要计算每个 元素的重复次数 k，利用 set 结构就可以

赏

谢谢你请我吃糖果