如何在O(n)时间内找出1~n数组中缺失的两个数（禁用哈希表）

方法一：数学求和推导法 #

• 先计算1到n的理论总和：S = n*(n+1)/2，理论平方和：S2 = n*(n+1)*(2n+1)/6
• 遍历数组，算出实际总和sum和实际平方和sum2
• 设缺失的两个数为x、y，可得：
  • x + y = S - sum（记为sum_diff）
  • x² + y² = S2 - sum2（记为sum2_diff）
• 推导两数乘积：xy = (sum_diff² - sum2_diff) / 2
• 结合和与乘积，解二元一次方程：
  • 先算(x - y)² = sum_diff² - 4*xy，得到两数的差的绝对值，再结合sum_diff即可求出x和y。比如x = (sum_diff + sqrt(sum_diff² - 4*xy)) / 2，y = sum_diff - x

举个实际例子：n=5，数组是[1,3,4]，缺失2和5

• S=15，sum=8 → sum_diff=7
• S2=55，sum2=1+9+16=26 → sum2_diff=29
• xy=(49-29)/2=10
• 解x+y=7、xy=10，得到x=2，y=5

方法二：异或法（避免大数溢出） #

当n很大时，平方和可能超出数值范围，异或法更可靠：

• 先异或1到n的所有数，再异或数组里的所有数，最终结果xor_total = x ^ y（其他数都出现两次，异或后抵消为0）
• 找到xor_total中任意一个为1的二进制位（比如取最右边的1，用mask = xor_total & -xor_total获取）
• 再次遍历1到n和数组，按该二进制位将数分成两组：位为1的一组，位为0的一组，分别对两组做异或操作：
  • 两组的异或结果就是x和y（因为x和y在该位上必然不同，会被分到不同组，其他数每组都出现两次，异或后抵消）

伪代码示例：

def find_missing_two(arr, n):
    xor_total = 0
    # 异或1~n和数组元素
    for i in range(1, n+1):
        xor_total ^= i
    for num in arr:
        xor_total ^= num
    # 获取最右侧的1作为分组掩码
    mask = xor_total & -xor_total
    x, y = 0, 0
    # 分组异或
    for i in range(1, n+1):
        if i & mask:
            x ^= i
        else:
            y ^= i
    for num in arr:
        if num & mask:
            x ^= num
        else:
            y ^= num
    return (x, y)

两种方法都是O(n)时间复杂度、O(1)空间复杂度，完全满足题目要求，不需要使用哈希表。

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