题目
数组nums包含从0到n的所有整数，但其中缺了一个数。请编写代码，找出那个缺失的整数，并在O(n)时间内完成。
示例 1：
输入：[3, 0, 1]
输出：2示例 2：
输入：[9, 6, 4, 2, 3, 5, 7, 0, 1]
输出：8
异或法
本题可以利用异或运算的性质，即：任何数与0异或都等于本身，任何数与自身异或等于0，以及异或运算的交换律和结合律。使用异或法求解本题的主要步骤如下。
1、异或所有数组元素。
2、继续异或所有从0到n的整数。
3、最终结果即为缺失的数字，因为其它数字都被异或消除了。
注意：因为for循环中只遍历了0到n-1这n个数，并没有遍历n，故我们将missing的初始值设置成了n。
根据上面的算法步骤，我们可以得出下面的示例代码。
def missing_number_by_xor(nums):
n = len(nums)
missing = n
for i in range(n):
missing ^= i ^ nums[i]
return missing
print(missing_number_by_xor([3, 0, 1]))
print(missing_number_by_xor([9, 6, 4, 2, 3, 5, 7, 0, 1]))高斯求和法
本题可以利用数学中的高斯求和公式，快速计算出从0到n的和，然后减去数组元素之和，从而得到缺失的数字。使用高斯求和法求解本题的主要步骤如下。
1、首先，计算数组元素之和。
2、利用公式(n*(n+1))/2，计算出从0到n的理论和。
3、两者之差，即为缺失的数字。
根据上面的算法步骤，我们可以得出下面的示例代码。
def missing_number_by_gauss_sum(nums):
n = len(nums)
expected_sum = (n * (n + 1)) // 2
actual_sum = sum(nums)
return expected_sum - actual_sum
print(missing_number_by_gauss_sum([3, 0, 1]))
print(missing_number_by_gauss_sum([9, 6, 4, 2, 3, 5, 7, 0, 1]))哈希法
本题还可以使用哈希法求解，其基本思想是：遍历整个数组，将每个元素添加到哈希表中；由于数组应该包含从0到n的所有整数，我们可以再遍历一次从0到n的范围，查找哈希表中未出现的数字，该数字即为缺失的整数。使用哈希法求解本题的主要步骤如下。
1、初始化一个空的字典。
2、遍历输入数组，对于数组中的每个元素，将其作为键添加到字典中，值可以任意。通常不需要存储值，这里只是为了标记存在。
3、遍历从0到n（包括n本身）的整数，检查每个数字是否在哈希表中。如果发现某个数字不在哈希表中，则该数字即为缺失的整数，返回该数字。
根据上面的算法步骤，我们可以得出下面的示例代码。
def missing_number_by_iteration(nums):
num_dict = {}
for num in nums:
num_dict[num] = True
n = len(nums)
for i in range(n + 1):
if i not in num_dict:
return i
print(missing_number_by_iteration([3, 0, 1]))
print(missing_number_by_iteration([9, 6, 4, 2, 3, 5, 7, 0, 1]))总结
以上三种方法均满足时间复杂度O(n)的要求，但三种方法适用的场景各有不同。
异或法简单高效，尤其适用于数值范围较大的情况，因为它避免了大数的直接计算。但该方法仅适用于特定场景，特别是当输入数据具备某种对称性时。
高斯求和法比较直观，适用于对异或操作不太熟悉的情况。但在数值非常大时，直接计算总和可能会有溢出的风险。
哈希法实现直观，易于理解和编码，能够处理更广泛的问题。比如：不仅可以找出缺失的数字，还能应对数字重复或其他更复杂的变异问题。但该方法需要额外的空间来存储哈希表，空间复杂度较高。
