如何优化Java嵌套循环，实现整数列表匹配对统计时间复杂度降至O(n)

优化方案 #

存在O(n)时间复杂度的实现方案，核心思路是先统计每个整数的出现频次，再通过组合数公式直接计算每个整数贡献的匹配对数，最终求和得到总匹配数。

实现原理 #

如果某个整数在列表中一共出现了k次，那么它能形成的两两不重复匹配对的数量为组合数 C(k,2) = k*(k-1)/2，无需嵌套遍历即可直接计算该值。

Java 实现代码 #

import java.util.HashMap;

int[] arr = new int[n];
int total = 0;
// 用HashMap统计每个数字的出现频次
HashMap<Integer, Integer> countMap = new HashMap<>();
for (int num : arr) {
    countMap.put(num, countMap.getOrDefault(num, 0) + 1);
}
// 遍历频次计算总匹配数
for (int count : countMap.values()) {
    total += count * (count - 1) / 2;
}

复杂度说明 #

• 时间复杂度：仅需两次线性遍历，整体为O(n)
• 空间复杂度：需要额外的哈希表存储频次，最坏情况（所有元素都不重复）下为O(n)，属于空间换时间的常规优化，在n较大时性能收益远高于原有O(n²)实现。

内容的提问来源于stack exchange，提问作者Gbeck