【算法解析】巧用哈希表与组合公式：高效统计数组中相同数对的数量

发表于 分类于 ， 阅读次数： Disqus： 本文字数： 924 阅读时长 ≈ 3 分钟

现有以下题目：1512. 好数对的数目
现有一个整数数组，要求统计数组中满足条件的索引对 (i, j)（其中 i < j 且 nums[i] = nums[j]）数量。

一、暴力循环

两层for循环可以遍历所有的索引对，但它的时间复杂度是O(n^2)，空间复杂度是O(n)。代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int numIdenticalPairs(vector<int>& nums) {
        int ans = 0;
        for(int i=0;i<nums.size(); i++){
            for(int j=i+1;j<nums.size(); j++){
                if(nums[i]==nums[j])
                    ans++;
            }
        }
        return ans;
    }
};

有没有办法能把时间复杂度降到O(n)。

二、组合公式+哈希表

输入：nums = [1,2,3,1,1,3]
输出：4
解释：有 4 组好数对，分别是 (0,3), (0,4), (3,4), (2,5)

根据上述示例，我们可以对问题进行分解，先计算关于1，再计算关于2的对数，再计算关于3的对数。

对于每个数字出现的次数：我们可以使用组合数公式直接计算出该数字包含多少对：

  • 当数组中某个数字出现1次时，代表该数字没有满足条件的索引对
  • 当数组中某个数字出现2次时，代表该数字有1对满足条件的索引对
  • 当数组中某个数字出现3次时，代表该数字有3对满足条件的索引对
  • 当数组中某个数字出现4次时，代表该数字有6对满足条件的索引对
  • …
  • 当数组中某个数字出现n次时，代表有$\frac{n*(n-1)}{2}$对满足条件的索引对

上述公式表示n个元素中选取 2 个的组合数，更用法的公式如：从n个元素选出m个元素的公式为：
$$\frac{n!}{m!(n-m)!}$$

我们只需计算出给定数组中不同数字的组合数并相加就能得到答案。
使用哈希表（如 std::unordered_map）遍历数组，记录每个数字出现的次数，时间复杂度O(n)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
#include <vector>
#include <unordered_map>

int numIdenticalPairs(const std::vector<int>& nums) {
    std::unordered_map<int ,int> freq;
    for(int num : nums)
        freq[num]++;

    int count = 0;
    for(const auto& entry : freq){
        int v = entry.second;
        count += v * (v - 1) / 2; 
    }
    return count;
}

int main() {
    // 示例测试
    std::vector<int> nums = {1, 2, 3, 1, 1, 3};
    int result = numIdenticalPairs(nums);
    std::cout << "Number of identical pairs: " << result << std::endl; // 输出应为 4
    return 0;
}

上述代码中第二个for循环用了auto类型推导，关于它的详细用法可以参考：
[C++中auto类型推导的常见用法](https://wangjunstf.github.io/2025/09/18/cpp-zhong-auto-lei-xing-tui-dao-de-chang-jian-yong-fa/)

在这里它根据freq的元素类型推断entry的类型。

代码中的 entry 是一个​​常量引用​​，它指向 std::unordered_map<int, int> 中的一个键值对（std::pair）。更准确地说，它的类型是：

const std::pair<const int, int>&

下面是关键点的解析：

组成部分 含义 说明
​​const​​ 常量 表示不能通过 entry 修改 unordered_map 中的元素。
​​std::pair​​ 键值对 unordered_map 中的每个元素都是一个 pair 对象。
​​<const int, int>​​ 模板参数 pair 的第一个成员（first）是 ​​const int​​（键），第二个成员（second）是 ​​int​​（值）。
​​&​​ 引用 避免在循环中拷贝整个 pair 对象，提升效率。

在你的代码中：

  • entry.first 是键（即数组中的数字，例如 1, 2, 3），因为是 const，所以不可修改。
  • entry.second 是值（即该数字出现的频率，例如 3, 2, 1），这里被用来计算好数对的数量：count += v * (v - 1) / 2;。

这种使用 const auto& 来遍历关联容器的做法非常常见，因为它​​既安全又高效​​。

简单来说，entry 就像是 freq 这个哈希表中每个单元的只读视图，让你能安全地读取每个数字及其对应的出现次数。