如何以O(n)时间复杂度查找两个数组中仅有的两个重复整数？

当然可以做到O(n)时间复杂度，这里给你两种实用解法：

方法一：哈希集合（通用解法，空间O(n)） #

这是最直接且容易实现的方案：

• 先遍历第一个数组，把每个元素存入一个哈希集合（比如Python里的set，Java里的HashSet），插入操作的平均时间复杂度是O(1)，这一步总耗时O(n)。
• 接着遍历第二个数组，对每个元素检查是否存在于集合中：
  • 如果存在，说明这就是两个重复元素之一，直接记录下来。
  • 找到两个符合条件的元素后就可以提前终止遍历，不用走完整个数组。
    整个过程的时间复杂度严格是O(n)，两次线性遍历加上平均O(1)的哈希操作，完全满足要求。

方法二：位运算+数学推导（空间O(1)，仅适用于整数元素） #

如果要求额外空间为O(1)，可以结合求和与位运算实现，但只适用于元素是整数的场景：

1. 计算两个数组的总和：sum_total = sum(arr1) + sum(arr2)。由于两个重复元素a和b在合并数组中各出现两次，其余元素仅出现一次，因此sum_total = sum_unique + a + b，其中sum_unique是所有唯一元素的总和。
2. 找到a ^ b的结果：我们可以先将arr1的所有元素异或得到xor1，arr2的所有元素异或得到xor2，再将xor1与xor2异或，得到的是arr1独有元素与arr2独有元素的异或结果——这显然没用，换个思路：直接遍历arr2，同时维护一个异或值，遇到在arr1中存在的元素就加入异或，最终得到a ^ b。
3. 利用a ^ b中某一位为1的特性，将所有元素分为两组，每组分别异或即可得到a和b。

不过这个方法依赖整数特性，实现起来比哈希集合复杂。如果没有空间限制，哈希集合的方法是更稳妥的通用选择。

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