只出现一次的数字如何用异或求解？（LeetCode 136）

简化版

一个数组里，除了某一个元素只出现一次，其余元素都恰好出现两次，找出那个只出现一次的。用异或：把所有元素依次异或起来，出现两次的两两抵消（x^x=0），最后剩下的就是答案。一行搞定，O(n) 时间、O(1) 空间，不需要哈希表或排序。

详细版

int singleNumber(int[] nums) {
    int res = 0;
    for (int n : nums) {
        res ^= n;          // 逐个异或
    }
    return res;            // 成对的抵消，剩单独的
}

原理：异或满足 x^x=0、x^0=x、交换结合律。所有数异或，出现两次的变 0，只剩出现一次的。
为什么优于哈希表：哈希表法要 O(n) 额外空间，异或法 O(1) 空间。
复杂度：O(n) 时间、O(1) 空间。

完整版教学

一、暴力解法及其不足

最直接的想法：

哈希表计数：遍历统计每个数出现次数，找次数为 1 的。O(n) 时间但 O(n) 空间。
排序后找：排序 O(n log n)，相邻两两一组，落单的就是答案。破坏了原数组、也更慢。

题目往往追加要求「O(n) 时间、O(1) 空间、不改数组」，这时哈希和排序都不满足，必须用异或。

二、异或的三条性质

异或 ^（相同为 0、不同为 1）满足：

x ^ x = 0：任何数和自己异或得 0。
x ^ 0 = x：任何数和 0 异或不变。
交换律 + 结合律：a ^ b ^ c = c ^ a ^ b，异或的顺序随便打乱结果不变。

三、为什么把所有数异或就得到答案

因为满足交换结合律，可以把数组元素任意重排再异或。既然除了一个单独的，其余都成对出现，我们在脑海里把相同的两两凑到一起：

a ^ a ^ b ^ b ^ ... ^ single
= (a^a) ^ (b^b) ^ ... ^ single
= 0 ^ 0 ^ ... ^ single
= single

每一对相同的数异或成 0，一堆 0 再异或还是 0，最后 0 ^ single = single。成对的全被消掉，只剩下那个孤单的——就是答案。初始 res = 0，因为 0 ^ x = x 不影响起手。

四、异或法的普适性与变体

这类「找单独/落单元素」的题都是异或的主场，但变体的出现次数不同，解法要变：

136 本题：其余出现两次 → 直接全异或。
只出现一次的数字 II（137）：其余出现三次 → 异或抵消不了（三个相同异或还剩一个），要用「按位统计模 3」或位运算状态机。
只出现一次的数字 III（260）：有两个只出现一次、其余两次 → 先全异或得到「两答案的异或值」，再用 lowbit 分组分别异或。

所以见到「其余出现两次、找一个单独」立刻想异或；出现三次或有两个答案时要升级解法。

五、常见误区

误区 1：以为要先排序或用 Set。那样就丢了 O(1) 空间的优势，面试会被追问优化。
误区 2：初始值设成 nums[0] 还是 0。设 0 最稳妥（0^x=x）；设 nums[0] 再从下标 1 开始也对，但没必要。
误区 3：把异或和「求和相减」混。求和法（2*sum(set) - sum(nums)）也能解 136，但要额外 Set 空间且可能溢出，不如异或干净。

六、用抵消不变量走完整数组

异或解法不依赖相同元素相邻，因为交换律和结合律允许任意重排。遍历到位置 i 时，累计值等于前缀中所有出现奇数次元素的异或；出现两次的元素最终贡献 0。题设“其余恰好两次、一个恰好一次”让最终奇数集合只剩答案。

数组 [4, 1, 2, 1, 2]
初始 x = 0
读 4: x = 4
读 1: x = 4 ^ 1
读 2,1,2 后可重排为 4 ^ (1^1) ^ (2^2)
x = 4 ^ 0 ^ 0 = 4
整个过程无需排序或额外集合

校验维度	本题必须保持的结论
循环/递推不变量	累计 xor 始终等于已扫描前缀所有元素的异或，成对元素无论何时出现最终都会抵消。
边界条件	数组只有一个元素时直接留下该值；负数按补码逐位异或，代数性质不变。
复杂度与代价	一次扫描 O(n)，只维护一个整数 O(1)，不修改输入顺序。
自检方式	用最小输入、典型输入和触及边界的输入分别手推，结果应与定义一致。

这组推演的作用不是替代证明，而是把抽象规则落到每一步状态变化上。面试写完代码后，应主动指出不变量如何保证不漏解，以及边界为何不会越界或死循环。若手推结果与定义不一致，应先修正状态语义，而不是继续给代码打补丁。

七、面试现场如何验证这道题

位运算题的代码通常很短，真正容易错的是把数学整数、固定宽度位模式和语言移位规则混在一起。本题应先复述这条不变量：累计 xor 始终等于已扫描前缀所有元素的异或，成对元素无论何时出现最终都会抵消。只有代码的初始化、更新顺序和终止条件都维持它，样例通过才具有证明力。

典型路径从“数组 [4, 1, 2, 1, 2]”开始手推，最后应得到“整个过程无需排序或额外集合”。
边界复核：数组只有一个元素时直接留下该值；负数按补码逐位异或，代数性质不变。
代价复核：一次扫描 O(n)，只维护一个整数 O(1)，不修改输入顺序。
用全 0、只有一个 1、最高位为 1 三类位模式检查掩码。
涉及负数时把值写成固定宽度补码，确认使用 >> 还是 >>>。
涉及左移时检查移位距离和溢出后是否仍符合题目的位模式语义。

最后要主动构造一个“少写一次循环、改变一个不等号或交换两行更新就会失败”的反例。能说清反例破坏了哪条不变量，比只报出复杂度更能证明真正掌握了算法。

记忆钩子：本题的代码可以压缩，但“累计 xor 始终等于已扫描前缀所有元素的异或，成对元素无论何时出现最终都会抵消。”这条正确性主线不能省。

八、常见误区与追问

误区：异或抵消要求两个相同数字相邻。 交换律与结合律允许逻辑上重新分组，相邻与否不影响结果。
误区：把所有数相加再除以二也能得到答案。 求和法没有这样的直接等式，并且还可能整数溢出。
误区：该方法能处理任意出现次数。 它只能自动消掉偶数次；其余出现三次时必须按位模 3 或用状态机。
追问：若有两个只出现一次的数怎么办？ 先全异或得到 a^b，再按其中一个差异位分组，各组分别异或。
追问：为什么空间复杂度是 O(1)？ 累计状态只有一个固定宽度整数，不随数组长度增长。
追问：异或法会改变原数组吗？ 不会；算法只读遍历并更新局部累计变量。

九、加强记忆

只出现一次的数字（其余出现两次）= 全体异或。靠异或三性质 x^x=0、x^0=x、交换结合律：把所有元素异或，成对的两两抵消成 0，最后剩下的就是那个单独的数。一行 res ^= n，O(n) 时间、O(1) 空间，胜过哈希（O(n) 空间）和排序（O(n log n)）。牢记变体：出现三次用「按位模 3」（137），有两个答案用「先异或再按 lowbit 分组」（260）。

简化版

详细版