Easy

题目描述

给你一个整数数组 nums，请你返回其中好数对的数目。

如果 nums[i] == nums[j] 且 i < j，那么我们称 (i, j) 是一个好数对。

示例 1：

输入：nums = [1,2,3,1,1,3]
输出：4
解释：有 4 个好数对 (0,3), (0,4), (3,4), (2,5) ，下标从 0 开始

示例 2：

输入：nums = [1,1,1,1]
输出：6
解释：数组中的每一对数字都是好数对

示例 3：

输入：nums = [1,2,3]
输出：0

提示：

  • 1 <= nums.length <= 100
  • 1 <= nums[i] <= 100

解题思路

这个问题有两种主要的解决思路：

方法一：暴力枚举法 最直观的做法是使用双重循环，枚举所有的下标对 (i, j) 其中 i < j，检查 nums[i] 是否等于 nums[j]。这种方法简单易懂但时间复杂度较高。

方法二：计数法（推荐） 根据提示，我们可以统计每个数字出现的次数。对于出现 n 次的数字，它能组成的好数对数量为 n × (n-1) / 2。这是因为从 n 个相同的数字中选择 2 个的组合数公式 C(n,2) = n!/(2!(n-2)!) = n×(n-1)/2。

具体实现时，我们可以用哈希表统计每个数字的出现次数，然后对每个数字计算其贡献的好数对数量，最后求和即可。

另一种实现方式是边遍历边计算：当我们遍历到某个数字时，它与之前出现的相同数字都能组成好数对，这样可以在一次遍历中完成计算。

推荐使用计数法，因为它的时间复杂度更优，且思路清晰。

代码实现

class Solution {
public:
    int numIdenticalPairs(vector<int>& nums) {
        unordered_map<int, int> count;
        int result = 0;
        
        for (int num : nums) {
            result += count[num];
            count[num]++;
        }
        
        return result;
    }
};

class Solution:
    def numIdenticalPairs(self, nums: List[int]) -> int:
        count = {}
        result = 0
        
        for num in nums:
            result += count.get(num, 0)
            count[num] = count.get(num, 0) + 1
        
        return result

public class Solution {
    public int NumIdenticalPairs(int[] nums) {
        Dictionary<int, int> count = new Dictionary<int, int>();
        int result = 0;
        
        foreach (int num in nums) {
            if (count.ContainsKey(num)) {
                result += count[num];
                count[num]++;
            } else {
                count[num] = 1;
            }
        }
        
        return result;
    }
}

var numIdenticalPairs = function(nums) {
    const count = new Map();
    let result = 0;
    
    for (const num of nums) {
        result += count.get(num) || 0;
        count.set(num, (count.get(num) || 0) + 1);
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)只需要遍历数组一次，哈希表操作为O(1)
空间复杂度O(k)k为数组中不同数字的个数，最坏情况下为O(n)

相关题目