数组中缺失数字的Python算法问题求助（求最优复杂度）

你的代码只适配数组有序且缺失元素在中间的场景，一旦出现以下两种情况就会失效：

1. 缺失的是最后一个元素（比如N=5，数组是[1,2,3,4]），你的循环里所有元素都等于i+1，missingNumber会保持初始值0，返回错误结果。
2. 数组无序（题目没要求输入数组是有序的！），比如N=5，数组是[2,1,5,3]，你的代码会在i=0时判定2≠1，直接返回1，但实际缺失的是4。

以下两种方法都是时间复杂度O(n)、空间复杂度O(1)的最优解，能适配所有测试用例：

方法1：求和差值法 #

核心思路：计算1到N的理论总和，减去数组所有元素的实际和，差值就是缺失的数字。
1到N的总和公式为 n*(n+1)//2（高斯求和公式）。

代码实现：

def MissingNumber(self, array, n):
    total = n * (n + 1) // 2
    sum_array = sum(array)
    return total - sum_array

说明：Python的整数是任意精度的，不用担心大数溢出问题，写法简洁直观。

方法2：异或法 #

利用异或运算的两个关键性质：

• 相同数字异或结果为0
• 0与任何数字异或结果为该数字本身

先异或1到N的所有数字，再异或数组中的所有数字，最终结果就是缺失的数字（其余数字都被异或两次，相互抵消为0，剩下的就是唯一没被抵消的缺失数）。

代码实现（两次循环版）：

def MissingNumber(self, array, n):
    xor_total = 0
    # 异或1到n的所有数
    for i in range(1, n+1):
        xor_total ^= i
    # 异或数组中的所有数
    for num in array:
        xor_total ^= num
    return xor_total

或者优化为一次循环：

def MissingNumber(self, array, n):
    xor_result = 0
    for idx in range(len(array)):
        # 异或当前索引对应的理论值（idx+1）和数组元素
        xor_result ^= (idx + 1) ^ array[idx]
    # 最后异或上n，因为数组长度是n-1，循环未覆盖到n
    xor_result ^= n
    return xor_result

说明：异或法的优势是完全避免了整数溢出风险，在Java/C++等语言中更实用，Python中两种写法都能稳定运行。

用你的示例测试用例验证：

Input: N=5, A[]={1,2,3,5}
Output:4

• 求和法：1到5总和15，数组元素和11，15-11=4，正确。
• 异或法：1²3⁴5 =1，数组元素异或1²3^5=5，15=4，正确。

再测试边界场景：

• N=5，数组={1,2,3,4}，缺失5：求和法返回15-10=5，异或法返回(1²3⁴5)⁽¹2³4)=5，正确。
• N=5，数组={2,1,5,3}，缺失4：求和法返回15-11=4，异或法返回(1²3⁴5)⁽²1⁵3)=4，正确。

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