缺失数字如何用异或或求和找出来？（LeetCode 268）

简化版

数组 nums 长度为 n，包含 [0,n] 中除了一个缺失值之外的所有数字。最稳的位运算做法是把 0..n 和数组元素全部异或，成对出现的数字会抵消，最后剩下的就是缺失数字。时间复杂度 O(n)，额外空间 O(1)，并且没有求和溢出的风险。

详细版

int missingNumber(int[] nums) {
    int x = nums.length;
    for (int i = 0; i < nums.length; i++) {
        x ^= i;
        x ^= nums[i];
    }
    return x;
}

异或满足 a ^ a = 0、a ^ 0 = a、交换律和结合律。
0..n 中除了缺失数字外，其余数字都会在「下标或初始值」和「数组元素」中各出现一次。
也可以用高斯求和：n*(n+1)/2 - sum(nums)，但在固定宽度整数里要注意溢出。
面试优先讲异或版，因为它空间 O(1)，不需要排序，不修改原数组，也能自然避开求和溢出。

完整版教学

一、题目真正考的是“全集减现集”

这道题表面是在找一个缺失数字，本质是比较两个集合：理论全集是 0,1,2,...,n，实际数组少了其中一个。只要能让相同元素互相消掉，剩下的就只能是缺失值。排序、哈希表、求和、异或都在做这件事，只是成本不同。

用例 nums = [3,0,1]，长度 n=3，理论全集是 [0,1,2,3]。实际数组里有 0,1,3，缺的是 2。面试里先把问题抽象成「全集与现集做差」，后面的位运算才不会显得像背技巧。

二、为什么异或能表达“做差”

异或不是集合差运算，但在「每个正常数字出现两次、答案出现一次」的条件下，它刚好能完成抵消。把全集和数组全部异或：

0 ^ 1 ^ 2 ^ 3 ^ 3 ^ 0 ^ 1
= (0^0) ^ (1^1) ^ (3^3) ^ 2
= 0 ^ 0 ^ 0 ^ 2
= 2

这里依赖的是异或的三条性质：相同为 0，0 不影响结果，顺序可交换。也就是说，数组不需要有序，下标和元素也不需要一一对应，只要所有非缺失数字最终都出现偶数次就会消掉。

记忆钩子：缺失数字的异或法不是“神奇公式”，而是把 0..n 和 nums 放进同一个抵消池，成对的走掉，落单的留下。

三、为什么初始化为 n 很自然

代码通常写成 x = n，循环里异或 i 和 nums[i]。这样做的原因是循环下标只覆盖 0..n-1，而理论全集还包含一个 n。把 n 先放进 x，就相当于先把全集最后一个元素加入抵消池。

以 nums=[3,0,1] 为例：

初始 x = 3
i=0: x = 3 ^ 0 ^ 3 = 0
i=1: x = 0 ^ 1 ^ 0 = 1
i=2: x = 1 ^ 2 ^ 1 = 2
返回 2

这个过程也能解释边界：如果缺失的是 n，例如 nums=[0,1,2]，循环里的 0,1,2 都会被数组元素抵消，初始留下的 n=3 最后返回；如果缺失的是 0，初始 n 会被数组中的 n 抵消，其他数字也抵消，最后返回 0。

四、异或法、求和法、哈希法怎么选

方法	时间复杂度	额外空间	关键风险	面试评价
哈希集合	O(n)	O(n)	空间浪费	容易想到，但不是最优
排序	O(n log n)	取决于排序	修改数组或变慢	可作为过渡思路
高斯求和	O(n)	O(1)	固定宽度整数可能溢出	简洁，但要解释边界
异或抵消	O(n)	O(1)	要讲清楚抵消池	最推荐

如果语言整数不会溢出，求和法也很优雅；但在 Java、C++ 里，n*(n+1)/2 在大范围下可能超过 int。异或只关心位模式，避免了大数求和风险，所以更适合作为算法面试的主答案。

五、复杂度与正确性不变量

循环不变量可以这样说：处理到下标 i 之后，x 等于「已经放入抵消池的理论数字」与「已经扫描过的数组数字」的异或结果。每个非缺失数字最终进入两次，贡献为 0；缺失数字只从理论全集进入一次，贡献为它自己。

公式写成：

x = (0 ^ 1 ^ ... ^ n) ^ nums[0] ^ nums[1] ^ ... ^ nums[n-1]

因为除了 missing 之外的每个数字都出现两次，最终只剩 missing。循环只扫描一次数组，所以时间 O(n)；只维护一个整数变量，所以空间 O(1)。

六、常见边界怎么手动验证

边界验证不要只测中间缺失。至少准备这几类输入：

nums = [0]       n=1, 缺 1
nums = [1]       n=1, 缺 0
nums = [0,1,2]   n=3, 缺 3
nums = [3,0,1]   n=3, 缺 2

这些用例分别覆盖缺最后一个、缺第一个、数组已经升序、数组乱序。能通过这些例子，说明你的初始化、循环范围和抵消逻辑都没有偏移一位。

七、常见误区与追问

误区：把 x 初始化为 0 后只异或下标和元素。 这样会漏掉理论全集里的 n，当缺失值不是刚好被其他错误抵消时会返回错值。
误区：认为数组必须先排序。 异或满足交换律和结合律，抵消不依赖相同数字相邻。
误区：求和法永远比异或法更好。 求和法简洁，但固定宽度整数里可能溢出；异或法不累加数值大小。
追问：如果数组里有重复数字还缺一个数字怎么办？ 原题保证互不相同；若有重复又缺失，通常需要同时找重复和缺失，不能直接套本题异或。
追问：为什么负数不需要讨论？ 原题数字范围是 [0,n]，不存在负数；若扩展到任意整数集合，仍要明确全集定义。
追问：为什么空间复杂度是 O(1)？ 只维护一个固定宽度整数 x，没有随 n 增长的数据结构。

八、加强记忆

缺失数字 = 「全集 0..n」和「数组现集」做抵消。代码里 x = n 是为了补上循环下标没有覆盖的最后一个理论数字；循环中每轮执行 x ^= i; x ^= nums[i];，所有正常数字出现两次被消成 0，缺失数字只出现一次就留下。求和法也能做，但异或法更适合强调 O(n) 时间、O(1) 空间和无求和溢出。

简化版

详细版