数组中寻找唯一数对的时间复杂度：是否存在优于O(n)的解法？

首先直接给结论：不存在时间复杂度优于O(n)的解决方案，下面我来详细解释原因，同时给出一个高效的O(n)实现示例。

为什么无法超越O(n)？ #

要解决这个问题，我们的核心需求是确定数组中每个元素的出现次数——只有知道某个元素恰好出现2次，才能判定它属于“唯一数对”。而要做到这一点，任何算法都必须至少遍历数组中的每一个元素一次：

• 如果跳过了哪怕一个元素，你就无法准确知道该元素的出现次数，也就无法排除它可能符合条件的情况（比如跳过的元素是某个只出现2次的元素中的一个，你就会漏判）。
• 这意味着问题的时间复杂度下界是Ω(n)，也就是说最优的时间复杂度就是O(n)，不可能找到比这更快的算法。

一个高效的O(n)实现示例 #

最直接的方式是用哈希表（字典）统计每个元素的出现频率，然后筛选出频率恰好为2的元素。以下是Python的实现代码：

def find_exact_two_occurrences(arr):
    frequency = {}
    # 遍历数组统计频率
    for num in arr:
        frequency[num] = frequency.get(num, 0) + 1
    # 筛选出恰好出现2次的元素
    return [num for num, count in frequency.items() if count == 2]

# 测试题目中的示例数组
sample_arr = [1, 4, 2, 3, 3, 2, 4, 1, 3, 6, 6, 5, 6, 6]
print(find_exact_two_occurrences(sample_arr))  # 输出: [1, 4, 2]

这个解法的时间复杂度是严格的O(n)：遍历数组一次是O(n)，遍历哈希表筛选结果是O(k)（k是数组中不同元素的数量，k≤n），整体还是O(n)。空间复杂度是O(k)，用于存储每个元素的频率。

如果数组中的元素范围是已知的有限整数，也可以用数组代替哈希表来优化空间，但时间复杂度依然是O(n)，不会更低。

补充说明 #

可能有人会想能不能用位运算来优化，但位运算通常适用于寻找出现奇数次的元素（比如只出现一次的元素），对于“恰好出现2次”的需求，位运算无法直接区分“出现2次”和“出现4次、6次”等偶数次的情况，所以哈希表统计是最直观且高效的方式。

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