用于计算数组中相同元素对的数量的高效算法

Question

例如，

int num[] = {1, 5, 3, 12, 5, 1, 4};
int len = 7;
int count = 0;

（假设数组中的相同元素不超过2个）
那么我会做

for(int i=0; i<len-1; i++) {
  for(int j=i+1; j<len; j++) {
    if(num[i] == num[j]) {
      count++;
    }
  }
}  

那么计数将为2。

但是该算法导致了O（N ^ 2）的效率。
有没有更有效的方法？
先感谢您！

Answer 1

比O(n log n)排序快，使用哈希表。其结构为线性或O(n); 每次插入时，遍历输入数组时，您都可以测试（以常数，O(1)成本为单位）哈希表中是否已存在该键，  即 “对”。当您发现这种“匹配”情况时，您将增加一个计数器。遍历数组后，计数器会告诉您答案。