企业官网建设流程全解析

如果让我在算法题里挑一道"面试撞车率"最高的题目，LeetCode 136题"只出现一次的数字"绝对排得上号。我第一次遇到它是在一场远程面试里，面试官让我共享屏幕写代码，题目读完，我的第一反应是开一个哈希表数次数——写了三行被叫停，他说："线性时间复杂度我忍了，常数空间怎么保证？"那一刻我意识到，这道题考的不是你会不会数数，而是懂不懂位运算底层那层窗户纸。

这道题的题干非常简洁：给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次，找出那个只出现了一次的元素。要求线性时间复杂度，并且尽量不使用额外空间。如果你还没刷过这道题，或者刷过但没理解透彻，这篇内容应该能帮你把异或解法彻底搞明白，顺便把两道经典变体题也一并拿下。对于刚入门算法题的新手来说，它是一个极好的位运算启蒙案例；对于准备面试的开发者来说，它又是一个高频得不能再高频的考点。

1. 这道题的"一眼暴力"与"一眼最优"之间，差一个异或

1.1 先看清题目：到底在问什么

题目给了一个非空整数数组，比如[2, 1, 4, 1, 2]，除了4只出现一次，其他数字都恰好出现两次。要求你把这个落单的4找出来。

这里有两个关键词值得圈出来。

第一个是"非空"。这意味着你不用处理空数组的边界情况，代码写起来可以少一层判断。

第二个是"恰好两次"。这个限制条件才是整个题目的题眼。它把这道题从一道普通的查重题，变成了一道标准的位运算入门题。如果没有"恰好两次"这个限制，比如改成"其余每个元素均出现三次"，那异或解法直接失效，得换一套完全不同的思路。这一点后文会专门展开。

你还要注意题目的进阶说明：你的算法应该具有线性时间复杂度。你可以不使用额外空间来实现吗？"不使用额外空间"就是整个题眼。哈希表可以轻松做到时间 O(n)，但空间也到了 O(n)，直接不符合要求。

我用生活中的场景做个类比：假设你有一盒袜子，所有袜子都是成双成对的，只有一只落了单。现在要求你不看标签、不拆包装，用最快的方式找出那只落单的袜子。如果你逐一对比，那就是暴力法；如果你拿个本子记录每只袜子的颜色和款式，那就是哈希表法；但真正的高手会直接对袜子做"异或"操作——成双的自然抵消，剩下的就是落单的那只。

1.2 常规解法为什么被"常数空间"卡住

我刚开始刷题的时候，面对"找出只出现一次的数字"这种题目，脑子里冒出来的全是常规武器，但它们各自都有毛病。

第一种是哈希表法。遍历一次数组，把每个数字的出现次数记录在哈希表里，最后遍历哈希表，找到值为 1 的键。这个方案时间 O(n)、空间 O(n)，思路直白，相信很多人第一反应都是它。但它不满足"不使用额外空间"的要求，面试时只能作为"我们先聊一个可行解"的铺垫，不能作为最终答案。

第二种是排序法。先把数组排序，排序后相同的数字会相邻，然后一次线性扫描，发现某个数字和前后都不相同，就找到了答案。这个方法空间可以做到 O(1)（原地排序的话），但时间变成了 O(n log n)，不符合线性时间复杂度的要求。

第三种是暴力双重循环。每取一个数，就在整个数组里数它出现了几次，直到找到只出现一次的数。时间 O(n²)，空间 O(1)。写起来简单，但毫无技巧可言，大概率会挂在性能要求上。

也就是说，常规思路要么在空间上超了，要么在时间上超了。这道题之所以经典，就是因为它逼着你跳出"统计次数"的思维定式，去位运算里找答案。而位运算里恰好有一个操作符天生就是为这种场景准备的——异或。

2. 为什么异或能解题：从位运算底层说起

2.1 异或的三条铁律，以及那个开关灯类比

异或运算的符号是^，它的规则可以总结成一句话：相同为 0，不同为 1。这句话对应到具体运算上，就是下面三条铁律。

第一条，归零律：a ^ a = 0。任何一个数字和自己异或，结果一定是 0。

第二条，恒等律：a ^ 0 = a。任何一个数字和 0 异或，结果还是它自己。

第三条，交换律与结合律：异或运算满足交换律和结合律，也就是说a ^ b ^ c和c ^ b ^ a结果相同，括号怎么加也都一样。

这三条铁律如果你觉得抽象，可以想象一个开关灯的场景。一盏灯有两种状态，按一次开关，灯从灭变亮；再按一次，灯从亮变灭。按两次等于没按，这就是归零律；按零次灯保持原状态，这就是恒等律。二进制位上的异或运算，本质上就是这种"翻转"逻辑：你拿一个 1 去翻转某一位，拿一个 0 就保持不变。

2.2 把三条铁律用在数组上，手算给你看

有了这三条铁律，解题思路就顺理成章了：把数组里所有数字全部异或一遍，成对的数字会通过归零律抵消成 0，剩下的就是那个只出现一次的数字。

我拿[2, 1, 4, 1, 2]手算一遍：

2 ^ 1 ^ 4 ^ 1 ^ 2 = (2 ^ 2) ^ (1 ^ 1) ^ 4 // 利用交换律和结合律，把成对的凑在一起 = 0 ^ 0 ^ 4 // 归零律，2^2=0，1^1=0 = 4 // 恒等律，0 ^ 4 = 4

最终结果就是4，和预期完全一致。整个过程核心思想就一句话：让成对的数字互相抵消，单身数字自然浮出水面。

这里有个值得注意的点：异或运算不要求你把数组里的成对数字物理上排在一起，因为交换律和结合律保证了，无论遍历顺序如何，最终结果都一样。这意味你只需要一次线性扫描，用一个变量累积异或结果，就能拿到答案。

2.3 为什么题目把条件定为"两次"这么巧

面试官喜欢这道题，就是因为"恰好两次"这个条件和异或的归零律完美契合。如果改成"其余元素均出现三次"，直接用异或立刻翻车——因为x ^ x ^ x = x，三个相同的数字异或等于它自己，归零律失效了。

这种"巧合"其实出题人精心设计的。异或天然擅长处理"偶数次"的去重问题，而题目恰好给了你"偶数次"，于是最优解被锁定为位运算。这也是为什么很多算法高手看到"成对出现"四个字，第一反应就是想异或——因为它已经成了一种条件反射式的思维模式。

顺带提一句负数的情况。在绝大多数编程语言里，整数以补码形式存储，负数参与位运算时，每个二进制位照常独立计算，异或的性质依然成立。所以这道题里即使数组里有负数，解法也完全不用改。我当时第一次写的时候还专门拿负数试了一个用例，确认无误后才放心。

3. 完整求解过程与代码实现

3.1 核心代码：真的就这几行

这道题的代码短到让很多第一次见到的人不敢相信。我用 Go 和 Python 各写一版，思路完全一样。

Go 版本：

func singleNumber(nums []int) int { ans := 0 for _, num := range nums { ans ^= num } return ans }

Python 版本：

def single_number(nums: list[int]) -> int: ans = 0 for num in nums: ans ^= num return ans

就这两段代码，一个循环，一个异或，完了。没有哈希表，没有排序，没有双重循环。这也正是这道题魅力所在：最优解往往不是写出来的，而是想出来的。

3.2 边界情况与测试用例

我建议你在本地多跑几个用例，尤其是下面这些边界场景。

第一个是数组只有一个元素的情况，比如[5]。此时循环会执行5 ^ 0 = 5，最终返回 5，正确。因为 0 是异或的恒等元，初始值设成 0 不会影响结果。

第二个是数组中存在负数的情况，比如[2, -3, 2]。按位异或后，2 ^ (-3) ^ 2 = -3，可以直接得到答案。负数在补码表示下参与位运算，每一位依然独立，不需要额外处理。

第三个是数组元素很大的情况。比如[2147483647, 1, 2147483647]，异或结果会正确输出 1。Python 里整数是任意精度的，异或运算同样支持；Go 里 int 类型通常是 64 位（取决于平台），也足够覆盖这道题常见的测试数据。

3.3 复杂度分析和"为什么要这么写"

时间复杂度是 O(n)，因为只有一个一次遍历，遍历 n 个元素。空间复杂度是 O(1)，因为只用一个变量ans保存累积异或结果，不随输入规模增长。这两个指标完美满足题目要求。

这里有一个小坑值得单独提一下：ans的初始值必须是 0，不能是别的。因为它依赖的是恒等律a ^ 0 = a。如果你把初始值设成 1，那么所有数字异或完等于正确答案再异或 1，结果就偏了。这个错误我在刚学这道题的时候犯过，调试了半天才发现是初始化的问题。

还有一个经验是：用循环变量名的时候，不要直接用n这种含义模糊的名字，像我上面这样用num会好一些。虽然代码很短，可读性也是工程的一部分。

4. 变体升级：出现三次和出现两次的攻防

面试官如果只问 136 题，大概率会在你给出异或解法后点点头，然后抛出一个变体："如果其他元素都出现三次呢？""如果只出现一次的数字有两个呢？"这时候才是真正拉差距的地方。

4.1 进阶版一：Single Number II，其余元素出现三次

题目变成了：给定一个整数数组，除了某个元素只出现一次以外，其余每个元素恰好出现三次，找出那个只出现一次的元素。

异或解法在这里彻底失效了，因为x ^ x ^ x = x，三个相同的数异或结果是自己，没法抵消。

我当时的第一个想法是位计数法。既然一个数字在 32 位二进制下每一位只有 0 或 1 两种可能，那我可以统计每一个二进制位上，所有数组元素里出现 1 的次数。对于某个位，如果这个位上 1 出现的次数不是 3 的倍数，说明只出现一次的那个数字在这一位上必然是 1；如果是 3 的倍数，说明那一位上应当是 0。

Python 实现：

def single_number_ii(nums: list[int]) -> int: ans = 0 for i in range(32): count = 0 for num in nums: count += (num >> i) & 1 if count % 3 != 0: if i == 31: ans -= (1 << 31) else: ans |= (1 << i) return ans

时间 O(32n)，也就是 O(n)，空间 O(1)。这个解法能过，但写起来稍微有点啰嗦。如果面试官让你继续优化，还能用三个变量ones、twos、threes做状态机，专门处理"每一位出现 3 次就归零"的逻辑。那个不展开讲了，属于进阶中的进阶，博客写太长反而容易劝退人。

这里要提醒一个 Python 特有的坑：Python 的整数没有固定位数限制，循环里ans |= (1 << i)构造的是正数，如果需要表示负数，必须在第 31 位（符号位）时单独处理，也就是代码里ans -= (1 << 31)这一个分支。我知道它看起来有点别扭，但这是 Python 大整数模型下绕不开的处理方式。

4.2 进阶版二：Single Number III，两个只出现一次的数字

另一道经典变体是：数组里有两个数字只出现一次，其余数字都出现两次，让你把这两个数字找出来。比如[1, 2, 1, 3, 2, 5]，答案是[3, 5]。

思路分四步走，我拆开来说。

第一步，全体异或。因为成对的数字在异或中互相抵消，最终得到的xor就是a ^ b，其中a和b是两个只出现一次的数字。

第二步，找到xor最低位为 1 的位置。这个位置的 1 意味着什么？意味着a和b在这个二进制位上不同，一个是 1，一个是 0。为什么？因为异或的结果是 1，代表两个数的这一位确实不相同。

第三步，用这个位置把原数组分成两组。分组规则是：这个位上是 1 的放一组，是 0 的放另一组。因为其他成对的数字在这一位上的值是相同的，所以它们会被分到同一组，不会串组；而a和b由于这一位不同，必定被分到不同组。

第四步，两组分别异或。每组里除了一开始就成对的数字互相抵消，剩下的就是只出现一次的那个数字。两组分别得到a和b。

代码实现：

def single_number_iii(nums: list[int]) -> list[int]: xor = 0 for num in nums: xor ^= num # 提取 xor 中最低位的 1 diff = xor & (-xor) a = b = 0 for num in nums: if num & diff: a ^= num else: b ^= num return [a, b]

这里xor & (-xor)是提取最低位 1 的经典写法。它利用了补码的特性：负数是正数按位取反再加一，一个正数和它的负数做按位与，结果恰好保留最低位的那个 1，其余位全变成 0。比如xor = 6，二进制是110，-xor的二进制是...1010，6 & (-6) = 2，也就是010，正好是最低位 1 所在的位置。

懂了这个技巧，很多类似的位运算题都能用上，我强烈建议你在编辑器里多打印几个数字验证一下，印象会深刻很多。

4.3 变体题的价值：面试官真正想考察什么

刷题刷多了你会明白，面试官出变体题，不是为了刁难你，而是想看看你的理解是不是只停留在背答案层面。你背下来 136 题的异或解法很容易，但能不能从"恰好两次"推导到"恰好三次""恰好两个"，直接反映了你懂不懂位运算的底层机制。

我后来参与过一些技术面试，经常看到候选人遇到变体就僵住。他们知道a ^ a = 0，但不知道为什么这个性质能被延伸到分组异或里。我觉得与其背题，不如把每道经典题的底层逻辑吃透，尤其是这种变体题的推导链条。面试时你可以不写最优解，但一定要有自己的思考过程，这个过程比代码值钱得多。

5. 这道题在真实工程中的影子

很多人觉得刷题归刷题，工程归工程，位运算这种东西在生产代码里用不上。这个想法太绝对了。异或运算在底层系统里几乎是"隐藏英雄"，只是平时你不会直接跟它打照面。

5.1 存储系统中的异或校验

最典型的案例是 RAID 5 磁盘阵列。RAID 5 会把数据分成多个块分布在不同的磁盘上，同时额外维护一份校验信息。这份校验信息怎么来的？就是通过对所有数据块做异或运算得来的。当某一块磁盘损坏时，系统用剩下的数据块和校验块做异或，就能把损坏磁盘上的数据恢复出来。

这个过程本质上就是"成对抵消，异或还原"的思路。和这道题的解法是一脉相承的。如果你能理解数组里的异或抵消，再看 RAID 的恢复原理就会觉得非常自然。

5.2 数据完整性与成对匹配检测

在网络传输或者文件存储中，有一种简单的校验方法叫奇偶校验。发送方把所有字节做异或运算，得到一个校验字节，跟着数据一起发出去；接收方拿到数据后重新算一遍异或，和收到的校验字节对比。如果不同，说明传输过程中数据出了问题，需要重传。

另外，在某些成对匹配的业务场景里，比如订单号配对、设备上下线记录配对，如果业务上能保证某个 ID 只会出现两次，你想快速找出那个出现奇数次（一次）的记录，异或同样是好帮手。这种场景最直接的优点是空间 O(1)，不需要额外存储一整套计数表。

5.3 从刷题到工程：什么该学，什么不该学

不过我也要泼一盆冷静水：在工程里，千万不要看到"成对出现"就条件反射地写位运算。异或代码虽短，但可读性差。你写个ans ^= num，旁边的同事大概率要愣一下才反应过来你在干什么。日常业务开发里，哈希表的可读性和可维护性远高于位运算，我实际工作中很少为了省一个哈希表的空间去引入这种晦涩代码。

那这道题到底该学什么呢？我觉得是那种"在限制条件下重新思考问题"的能力。当常规解法撞上性能瓶颈或者存储瓶颈时，能不能退一步，把问题放到更底层的维度重新审视。这种思维训练，才是刷题真正沉淀下来的东西。

最后再分享一个小体会。把 136 题吃透之后，我最大的收获其实是面对"成对出现"这类问题时，脑子里的第一反应从"数次数"变成了"能不能抵消"。这个转变在面试里救过我很多次，因为它能让你在别的候选人还在老老实实写哈希表的时候，直接给出一个让人眼前一亮的最优解。

我后来自己做代码审查，看到同事用位运算处理成对匹配的逻辑，也能一眼看出问题所在。这种感觉挺妙的——一道看似简单的题，带来的是一种"去底层找答案"的直觉。如果你也正在刷这道题，建议不要急着看答案，先自己憋 5 分钟，哪怕最终没想出来，再回头看异或解法，你的收获至少会翻一倍。