好数对的数目-LeetCode

1512. 好数对的数目

🎯 问题描述（来源于LeetCode）

描述：
给你一个整数数组 nums。
如果一组数字 (i, j) 满足 nums[i] == nums[j] 且 i < j，那么它就是一个好数对。
请你返回好数对的数目。

说明：

• 这是一个计数问题。

• 核心逻辑是统计每个数字出现的频率，然后利用组合数学公式计算好数对的数量。

• 对于出现 n 次的数字，其好数对的数量为 $C_n^2 = \frac{n(n-1)}{2}$。

• 示例：

• 示例 1：

输入：nums = [1,2,3,1,1,3]
输出：4
解释：
- (0,3) -> nums[0] == nums[3] == 1
- (0,4) -> nums[0] == nums[4] == 1
- (3,4) -> nums[3] == nums[4] == 1
- (1,2) -> nums[1] == nums[2] == 3
- 总共有 4 个好数对。

• 示例 2：

输入：nums = [1,1,1,1]
输出：6
解释：
- 数字 1 出现了 4 次，好数对数量为 C_4^2 = 4*3/2 = 6。

💻 解题思路

思路1：哈希表计数 + 组合数学

思路1：代码实现

class Solution:
    def numIdenticalPairs(self, nums: List[int]) -> int:
        count = 0
        # 使用 Counter 统计每个数字出现的次数
        idx = Counter(nums)
        
        # 遍历每个数字的出现次数
        for i in idx.values():
            # 如果某个数字出现次数大于 1，则可以形成好数对
            if i > 1:
                # 对于出现 i 次的数字，好数对数量为 C_i^2 = i*(i-1)/2
                # 代码中先计算 i*(i-1)，最后再除以 2
                count += (i-1) * i
        
        # 最后除以 2，得到最终结果
        return count // 2

思路1：📊 性能分析

• 时间复杂度：$O(N)$
  • 其中 $N$ 是数组 nums 的长度。
  • Counter(nums) 需要遍历数组一次，时间复杂度为 $O(N)$。
  • 遍历 idx.values() 的时间复杂度为 $O(K)$，其中 $K$ 是不同数字的个数，$K \le N$。
  • 总时间复杂度为 $O(N)$。
• 空间复杂度：$O(N)$
  • 哈希表 idx 在最坏情况下需要存储 $N$ 个键值对（当所有数字都不同时）。

思考

1. 组合数学原理：

   • 对于出现 i 次的数字，我们需要从 i 个位置中选择 2 个位置，且顺序固定（i < j）。
   • 这就是组合数 $C_i^2 = \frac{i(i-1)}{2}$。
   • 例如，数字 1 出现 3 次，好数对数量为 $C_3^2 = \frac{3 \times 2}{2} = 3$。

2. 代码优化：

   • 代码中先计算 (i-1) * i，最后再统一除以 2。
   • 这是一种常见的优化技巧，可以避免在循环中进行浮点数除法。
   • 由于 i(i-1) 一定是偶数（两个连续整数中必有一个是偶数），所以最后除以 2 不会丢失精度。

3. 替代解法：

   • 也可以使用双重循环暴力求解，时间复杂度为 $O(N^2)$。
   • 或者使用哈希表在遍历过程中动态计数，时间复杂度为 $O(N)$，空间复杂度为 $O(N)$。

4. 边界情况：

   • 数组长度为 1：没有好数对，返回 0。
   • 所有数字都不同：没有好数对，返回 0。
   • 所有数字都相同：好数对数量为 $C_N^2 = \frac{N(N-1)}{2}$。