又一次在题库里碰到第 136 题“只出现一次的数字”刚看到的时候很多人都会觉得简单——数组里除了一个元素其他都成对出现找孤例嘛。但真正动手之后才发现难点往往不在“找出答案”而是被一道限制卡得死死的线性时间复杂度常数空间复杂度。我见过不少同学先写哈希表再被一句“能不用额外空间吗”问住也见过有人闷头排序结果复杂度分析时自己摇头。这道题最有趣的地方在于它逼你去重新认识一个平时被忽视的运算符——异或。今天这篇文章我就把从读题到敲完代码的完整思路链梳理一遍顺便讲讲容易踩的边界坑、变体扩展以及这类题目在工程里的真实应用。1. 为什么第一反应的三个朴素解全都卡在复杂度线上拿到“只出现一次的数字”这类问题第一步不是急着写代码而是把题目的限制念三遍时间复杂度必须是 O(n)空间复杂度必须是 O(1)。这两个条件放在一起等于直接对大部分常规数据结构关上了门。新手最常见的三个方案分别是暴力遍历、哈希统计、排序后扫描。它们每一种都有合理的地方也确实能跑出正确结果但是在面试或竞赛环境下都会被同一个问题卡住要么时间超了要么空间超了。我先把这几个方案逐个拆开不是为了吐槽它们而是希望通过对比让大家理解为什么最后会走到位运算那条路上。1.1 暴力双循环小用例没问题数据稍大就崩最简单粗暴的想法是对数组里的每一个元素再完整扫一遍整个数组统计它出现了几次。遇到出现了两次的其他元素直接提前停下只有从头到尾都没有重复的那个家伙才是我们要的结果。写成伪代码就是两层循环内层里加一个计数器。这种做法的正确性毋庸置疑但时间复杂度是 O(n^2)。数组长度几千的时候还能忍一旦到了几十万、上百万循环次数会变成天文数字。在面试场景里这个方案一般只作为“我第一时间想到的最笨办法”提一句然后马上丢弃。真正值得记住的教训是拿到题目之后先把复杂度估算变成肌肉记忆不要觉得“能跑出结果就万事大吉”。我在练习时经常提醒自己一个方案的复杂度决定了它在真实数据里能不能活下来。题目数据范围是千级还是百万级直接决定了哪些解法可以进候选名单。1.2 哈希表统计思路直白空间代价却翻倍用哈希表记录每个元素出现的次数然后遍历一遍哈希表找到计数为 1 的元素。这是绝大多数人在数据结构课上学过的标准做法代码写起来也最顺手def single_number(nums): count {} for num in nums: count[num] count.get(num, 0) 1 for num, cnt in count.items(): if cnt 1: return num return -1时间上是 O(n)思路没有任何毛病。问题出在空间上你额外借用了一张和数组规模同级别的哈希表空间复杂度是 O(n)。而原题明确要求“不使用额外空间”。在面试场景里如果回答完哈希表解法之后被追问“能不能做到常数空间”你还没有备选方案这道题就等于砸了一半。我自己的体会是哈希表解法从来不是错解它是一个极好的兜底方案。平时做工程完全可以用它快速验证数据但刷题时它最容易被拿来当对照物——正因为有了 O(n) 空间的解法题目的 O(1) 空间限制才显得那么刻意。它更像是在提醒我们别满足于“能跑”要找到让数据结构和输入规模脱钩的解法。1.3 排序后相邻比较常数空间有了时间上限先超了第三种常见想法是先把数组排序。排完序后相同的元素一定紧挨在一起所以只要从头到尾扫描比较相邻的两个数是否相同就能在常数空间里找到那个唯一的元素。比如输入 [4,1,2,1,2]排序后变成 [1,1,2,2,4]两两比较后剩下 4。这个方案的时间复杂度取决于排序算法最快也是 O(n log n)比如快速排序、归并排序。虽然实际运行里 O(n log n) 看起来比 O(n^2) 体面很多但它依然不满足题目要求的线性时间。空间上它倒是很符合条件原地排序几乎不占用额外存储。在工程里排序后扫描是很实用的思路因为排序本身就是高频操作。但放到这道题里它被硬卡在了时间线上。如果你在这三个方案里循环打转就会陷入一种困境要么省时间费空间要么省空间费时间好像怎么都绕不过去。提示当一个算法题同时要求 O(n) 时间和 O(1) 空间而且数组元素全部成对出现就要立刻意识到“数学性质”比“数据结构”更适合解决问题。位运算尤其是异或就是这一类题最典型的突破口。2. 异或解法的完整拆解为什么一个变量就能跑完全程如果上面三个方案是常规路线那异或解法就是专门写给这道题的快速通道。它简单到令人怀疑一个变量初始为 0遍历每个数字做一次异或最后剩下的就是只出现了一次的数字。2.1 异或的三个特性与相消直觉异或运算XOR记作 ^本质上做的是“按位比较相同为 0不同为 1”。它有三个对解这道题至关重要的性质任何数异或 0结果还是它自己a ^ 0 a任何数异或自己结果为 0a ^ a 0异或满足交换律和结合律a ^ b ^ c 的计算结果和顺序无关把这三条合起来看就很容易理解解法数组里有 2 个 1、2 个 2那么对它们做任何顺序的异或1 和 1 会先撞在一起变成 02 和 2 也会变成 0那些成对出现的元素最终全部归零唯一落单的元素 a 从头到尾没有配对最后会以 a ^ 0 的形式保留下来。可以把它想象成一次“消消乐”异或的过程不关心元素在数组里的位置也不关心先后顺序只要是两个相同数值就能互相抵消。这个直觉一旦建立这题就不再是背代码而是真正看穿运算规则。2.2 手算一个完整例子拿经典输入 [4, 1, 2, 1, 2] 来走一遍ans 0ans ^ 4得 4ans ^ 1得 4 ^ 1 5ans ^ 2得 5 ^ 2 7ans ^ 1得 7 ^ 1 6这里 1 和 1 完成了抵消ans ^ 2得 6 ^ 2 4最终结果是 4跟肉眼观察一致。中间的数列看起来毫无规律但每一步都是确定的。正因为异或可交换、可结合你不需要去记忆哪两个数字已经“碰过面”运算过程自己会把它们消掉。这也是为什么只用一个变量就足够历史状态被压缩在 ans 里随时可以继续跟下一个数字合并。2.3 三种语言的落地代码Python 版def single_number(nums): ans 0 for num in nums: ans ^ num return ansC 版class Solution { public: int singleNumber(vectorint nums) { int ans 0; for (int num : nums) { ans ^ num; } return ans; } };Java 版class Solution { public int singleNumber(int[] nums) { int ans 0; for (int num : nums) { ans ^ num; } return ans; } };三份代码几乎长得一样核心都是同一个循环。时间复杂度 O(n)只做一遍遍历空间复杂度 O(1)只用一个普通变量。循环里临时变量的数量不随数组规模增长完全满足题目要求。2.4 为什么这种解法能同时满足两个限制对照前面的三个朴素解异或方案之所以能赢是因为它把“数组里成对元素”这个结构信息直接变成了运算规则数字相同异或结果为 0。它不需要额外存储统计数据不需要先排序改变数组结构更不需要反复扫描。一次遍历边读边消。说白了这类题考查的往往不是你会不会写循环而是你能不能从约束条件反推“应该调用哪种数学工具”。当数据元素具备“成对出现、自反抵消”特征时异或几乎是唯一的终极方案。面试的时候先把约束讲清楚再引出异或的三大性质最后落到代码整个逻辑链会非常顺畅。3. 边界情况与常见误区负数、0 和一万个整数真正写题时不少人顺利通过了示例却在隐藏用例上翻车。原因往往不是异或本身错了而是没有想清楚边界条件。我刚开始刷这类题时也踩过类似的坑所以专门把边界情况拎出来讲。3.1 数组只有一个元素比如输入 [7]异或过程的起点是 0唯一的数字和 0 异或后还是 7结果正确。这一点看起来很平凡但确实是边界用例里最容易验证的部分。空数组不需要考虑因为题目已经明确数组非空。不过我自己在本地调试时还是会写一层长度判断避免手滑测到空输入。很多隐藏用例报错都是因为测试环境里混入了一个不该出现的空数组这种小习惯能省不少排查时间。3.2 负数参与异或不要被符号位吓到很多初学者看到负数就犯怵觉得异或这种位运算只适合“无符号的正整数”。其实完全不是这样。在 Java 和 C 里整数以补码形式存储异或是按位进行的符号位也照常参与计算。比如 -1 的二进制表示是全 1-1 ^ 2 的结果是一个负数但这不影响解题因为异或的“相同为 0、不同为 1”对所有位一视同仁。举个实际例子输入 [-4, 3, -4]正常手推会发现两个 -4 抵消后剩下 3。程序不用做任何特殊处理负数也一样遵循 a ^ a 0。Python 更简单因为它使用任意精度整数负数的位运算语义也保持统一。这点和一些人担心的“Java 的 int 溢出会不会影响位运算”一样都不会影响这类题目的结果。所以请记住异或解法天然支持负数没必要为符号位额外写分支。如果面试官追问“负数怎么办”直接说明补码存储和逐位运算的机制即可。3.3 结果可能隐藏在高位不要跳步骤在面试手写这道题时我习惯在白板上顺手画一下二进制推导尤其是结果比较大的情况。比如输入 [1000000000, 1000000001, 1000000000]最终结果一眼看不出但按位推导就很清楚两个 1000000000 抵消剩下 1000000001。在实际编码中大部分语言直接返回整数即可不需要额外处理。Python 的 int 没有固定位宽Java/C 的 int 溢出在异或运算里仍然是可逆、对称的不会因为溢出改变正确答案。这里的经验是把“异或结果”当作一个不透明的整数来使用不要自作聪明地去截断位宽也不要试图把它强制转成无符号数再处理。3.4 常用自测用例清单输入数组预期结果备注[1]1单元素边界[1, 1, 2]2常规正数[-4, 3, -4]3负数参与[0, 0, 0]0结果为 0 的情况[1, 2, 3, 4, 1, 2, 3]4长度较大的混合[1000000000, 1000000001, 1000000000]1000000001大数值注意结果等于 0 时很多初学者会怀疑“是不是没找到”。这其实是完全合理的结果。只要数组中确实存在一个元素 0且其他元素成对出现最后的异或结果就等于 0。4. 一题变一类题异或思维的三种进阶延伸“只出现一次的数字”并不是孤案它背后是一整套“用位运算处理重复元素”的思考方式。掌握了这道题再去碰它的两个著名变体会顺畅得多。4.1 出现三次的变体位计数法如果题目改成“除了某个元素只出现一次其余每个元素出现三次”异或的简单消消乐就不够用了。因为三个相同数字异或的结果等于它自己而不是 0。这时要用的是另外一个思路统计每一位上 1 出现的次数。如果一个数字出现三次那么它在二进制每一位上贡献的次数也是 3 的倍数把所有位的计数对 3 取余剩下的就是那个落单的数字。以 Java 代码为例public int singleNumber(int[] nums) { int ans 0; for (int i 0; i 32; i) { int count 0; for (int num : nums) { count (num i) 1; } if (count % 3 ! 0) { ans | 1 i; } } return ans; }这里遍历 32 位把每一位的累计次数取模 3再拼回结果。虽然多了 32 倍常数但时间复杂度仍然是 O(32n)空间 O(1)。我一开始也死记这个写法后来想通了“按位计数取余”的本质遇到“出现四次”之类的变题也能马上把取模参数改掉。位计数法的适用场景比异或更广代价是代码长度明显增加面试时需要用几句话把思路讲清楚。4.2 两个元素只出现一次的变体分组异或另一道常见变体是数组里有两个元素都只出现一次其余元素成对出现要求把这两个元素找出来。思路是这样的先把整个数组异或一遍得到 a ^ b。因为 a 和 b 不同这个结果必不为 0。接着找到结果二进制中任意一个为 1 的位这一位能区分 a 和 b。用这一位把数组分成两组分别异或两组各自剩下的那个数就是 a 和 b。def single_numbers(nums): xor_all 0 for num in nums: xor_all ^ num diff xor_all (-xor_all) a, b 0, 0 for num in nums: if num diff: a ^ num else: b ^ num return [a, b]我复盘这道题时最大的感悟是异或不是只能找“唯一出现一次”的数它还能通过挑选一个区分位把数组一分为二这是对位运算能力的二次挖掘。分组的过程有点像把纠缠在一起的两根线分开先用整体的异或结果找到分歧点再按分歧点拆开各自独立消消乐。4.3 从“奇偶次数”推广到一般情形如果把出现次数从“两次”推广到“任意奇数次 k”异或解法依然适用因为奇数个相同的数字异或后还等于它自己偶数个会变成 0。于是“出现奇数次”这个条件天然适合用异或解决而“出现偶数次”的问题则需要反过来考虑要么统计出现次数要么用位计数做取模。这类规律的总结比单题更重要。我刷题时会把这类题目放进同一个分类标签位运算、重复元素、奇偶次数。以后再看到类似描述就能条件反射地往异或上靠。这种迁移能力才是刷题真正的收益单独背一道题的代码过两周大概率就忘了。5. 异或解法在日常工程里并不陌生真实场景的对照有人会觉得这种题纯粹是面试里的脑筋急转弯工程里根本用不到。这个观点我完全不认同。异或能做的事情在真实系统里到处都是只是平时不会贴着一个“136.只出现一次的数字”的标签出现而已。5.1 状态开关与权限位运算把一个整数当成一组开关每一位表示一个布尔状态异或可以用来做“切换”。比如想要翻转某个位不需要先读再写直接将该位和 1 异或即可。在嵌入式开发、配置管理、权限系统里这种位级开销极小的操作非常常见。如果你做过网络协议相关的开发也会发现很多包头里的校验字段会用异或来快速计算。它不需要乘法、加法那样复杂的硬件逻辑速度非常快特别适合在资源受限的设备上跑。我刚开始接触协议解析时看到校验算法里全是异或还有点意外后来才意识到这类操作在底层是最经济的选择。5.2 数据备份与恢复中的冗余思想异或还有一个非常实用的特性如果 c a ^ b那么 a c ^ bb a ^ c。这意味着你可以用一份异或结果作为“冗余信息”在丢失 a 或 b 时把它恢复出来。常见的例子是分布式存储里的备份思路两台机器放原始数据一台机器放异或结果任何一台坏了都能用另外两台异或恢复。这和刷题里 a ^ a 0 的思想完全一致只是在更大规模上使用而已。从中也能看出奥妙不在于异或这个运算符本身而在于“成对抵消”和“任意两个还原第三个”这两个数学性质。5.3 面试官真正想考察的东西回到“只出现一次的数字”本身。面试官让你做这道题核心目标通常不是看你会不会用哈希表而是想考察三件事能不能读懂题目的时间、空间复杂度限制能不能在限制下联想到位运算这种数学工具能不能把思路讲清楚而不是直接丢代码。我见过不少候选人代码写得快但被问“为什么异或对负数也有效”时卡住。这说明底层原理没吃透。反过来如果能从异或的三个性质一步步推导整个面试观感会完全不同。这道题最妙的地方就在这代码短得不能再短但围绕它的追问可以一直挖到计算机组成原理层面。6. 练完这道题之后我沉淀下来的三个做题习惯讲完原理和变体最后再说点我个人的小经验。这些习惯不一定都只跟这一道题有关但对以后做类似的算法题确实能省很多力气。6.1 每次拿到题先同时写下时间与空间约束我刷题最开始的半年经常只顾着“能不能跑通”忽略了复杂度。后来养成了一个习惯读题之后先把约束写在纸的左上角哪怕题目没有明说也自己问问“数据范围是多少”。如果这道题的数据是百万级那 O(n log n) 可能还可接受如果数据是十亿级排序方案基本直接出局。136 题最典型的地方就是把“线性时间 常数空间”两条线画得很清楚逼着你去找第三条路径。6.2 把“成对出现”归类为异或题的标准信号处理数组里的重复元素时我只要看到“其他数字都出现偶数次”“只有一个数字出现奇数次”这类描述就会立刻把异或列入候选解法。这不是死记硬背而是因为奇偶性和异或的数学性质天然绑定。类似地看到“出现三次取余”时会想到位计数看到“找两个唯一数字”时会想到分组异或。把题型信号和算法思想挂钩比背场景模板可靠得多。6.3 多写几行手算过程最后一条建议可能有点反直觉如果只在脑子里推演很容易漏掉负数和高位的情况。我强烈建议哪怕已经知道答案也把示例输入完整手算一遍从 ans 0 开始把每一步的异或结果都写出来。手算一次之后你会对“为什么 1 和 1 抵消”形成更深的肌肉记忆也更容易在后续变体里发现规律。这道题虽然简单却像一个相当精准的筛子滤掉了“只会背代码”的人留下了真正理解异或运算本质的人。这也是我为什么愿意花一整篇来拆它的原因。