难度: Easy
数组nums包含从0到n的所有整数，但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在O(n)时间内完成吗？
注意：本题相对书上原题稍作改动
示例 1：
输入：[3,0,1] 输出：2
示例 2：
输入：[9,6,4,2,3,5,7,0,1] 输出：8
Submission
运行时间: 25 ms
内存: 17.0 MB
class Solution:
def missingNumber(self, nums: List[int]) -> int:
N = len(nums)
return N * (N+1) // 2 - sum(nums)
Explain
题解的思路基于高斯求和公式。对于给定的n，从0到n的所有整数的和可以通过公式 S = n * (n + 1) / 2 计算出来。这个公式得到的是如果没有缺失数字时，数组应该有的总和。题解中通过计算这个理论上的总和，然后从中减去数组中所有数的实际总和，差值即为缺失的数字，因为只缺失了一个数字，所以这种方法可以准确找到缺失的数字。
时间复杂度: O(n)
空间复杂度: O(1)
# 定义一个求解类
class Solution:
def missingNumber(self, nums: List[int]) -> int:
# 计算数组长度
N = len(nums)
# 计算0到N的所有整数的理论总和
expected_sum = N * (N + 1) // 2
# 计算数组中所有数字的实际总和
actual_sum = sum(nums)
# 缺失的数字是理论总和与实际总和的差
return expected_sum - actual_sum
Explore
高斯求和公式S = n * (n + 1) / 2是计算连续整数和的一种非常高效的方法，它可以在常数时间内（O(1)复杂度）直接得到从0到n的所有整数的和。使用这个公式避免了使用循环来逐个加和，从而提高了算法的效率，尤其是在n较大时更为明显。相比其他可能需要O(n)时间复杂度的方法（如循环累加），高斯求和公式更为简洁和高效。
调用sum(nums)来计算数组的实际总和确实是一种简便的方法，其时间复杂度为O(n)，因为它需要遍历数组中的每一个元素进行求和。在数组非常大时，这种方法的性能瓶颈主要体现在对内存带宽的需求以及可能的运算时间。尽管如此，对于大多数实际应用场景，这种方法仍然是可行的。如果性能成为关键问题，可以考虑使用并行处理或优化的数据结构来加速求和过程。
题解中的方法假设数组nums是从0到n的整数缺失一个，且没有重复数字。如果数组中出现了重复数字，该方法将不再有效，因为重复的数字会增加实际总和，使得缺失数字的计算不准确。这种情况下需要其他算法，如使用哈希表来记录每个数字的出现次数，或者使用位运算等方法来处理含有重复数字的情况。