最近在整理 LeetCode 热题 100 的刷题笔记时又翻到了第 136 题“只出现一次的数字”。这道题在题解区被戏称为“位运算的见面礼”因为它的最优解短得让人怀疑自己看错了题——一个 for 循环、一个异或运算符完事。但恰恰是这种“简单”让它在面试里的出现频率居高不下不光是考查位运算基础更考验一个人能不能在暴力解法之外主动往更优的方向想一层。这篇就以这道题为主线把从暴力到最优的推理过程、异或运算的本质、面试现场可能踩的坑和延伸考点一次说清楚。适合读这篇的人不光是正在刷热题 100 的求职党还有那些刷了几十道题但一直对位运算“敬而远之”的朋友。看完你会明白位运算不是炫技它是在特定约束下最自然的思考路径。1. 题目全解析先搞清楚“只出现一次的数字”到底在考什么1.1 题目原文与核心考点先看原题描述给定一个非空整数数组除了某个元素只出现一次以外其余每个元素均出现两次。找出那个只出现了一次的元素。要求算法应具有线性时间复杂度且不使用额外空间。两个约束条件非常关键。“线性时间复杂度”意味着 O(n)把 O(n log n) 的排序做法一票否决“不使用额外空间”意味着 O(1) 空间把哈希表的一票否决。这两刀切下去剩下的可行空间已经非常小了。但很多第一次接触这道题的人容易本能地陷入惯性思维看到“找唯一出现一次的元素”第一反应就是“记次数”。于是哈希表方案立刻跳到脑子里再一看空间限制傻眼了。其实面试官想看到的恰恰是你能不能在被限制逼到墙角之后换一条完全不同的路——用数字本身的运算规则来解题而不是依赖外部存储。核心考点其实有四个层次能不能正确理解题目约束暴力以外的方案是否被主动考虑过知不知道异或运算的基本性质尤其是“任何数与自己异或等于 0”这条能不能把“抵消成对元素”这个抽象逻辑落地成严谨的代码能不能应对追问比如数组变成“其他元素出现三次”怎么办“两个只出现一次的数字”又怎么办。这道题从 LeetCode 易程度看只是简单题但它嵌套的考点密度一点也不简单。1.2 为什么它会进热题 100背后的筛选逻辑LeetCode 热题 100 的选品逻辑不是挑最难的题而是挑“面试中最高频、覆盖考点最典型”的题。136 题完美命中这三条第一它在位运算专题里属于最基本的“敲门砖”。不懂位运算的人做这道题会觉得自己用哈希表也做出来了只是空间不达标但一旦学会了异或解法你会突然打开一扇门——原来“成对出现”这么强的结构可以直接被运算本身消化掉。这种“原来还能这样想”的顿悟感对后续刷 137、260 这类进阶题特别有帮助。第二它的输入输出结构非常简单没有链表翻转、没有动态规划状态转移一个一维数组走天下。这就让它非常适合作面试中的“暖场题”或“压力题”面试官可以先让你 5 分钟写出来再逐步加条件追问考察你在约束变化时的应变能力。第三它的解法和数学、位运算深度绑定天然适合考察“计算机底层思维”。哈希表解法谁都会但异或解法能区分出你是不是真的从二进制角度理解过数据。而现代计算机的加法、减法、乘法最终都是位运算实现的这种底层思维在系统设计、性能优化、并发编程中都极其值钱。我自己的刷题节奏里一般把热题 100 按专题过位运算这块我强烈建议从 136 开始因为它的代码量最小、原理最容易讲清楚先用它建立信心再逐步增加复杂度。2. 解法选型从暴力到位运算的四层递进2.1 第一层暴力双层循环先保证能写对很多教学帖直接跳过暴力解法直奔异或我反而觉得暴力解法有必要写一遍不是为了用它而是为了让你体会“限制条件是如何倒逼你优化”的。暴力解法非常直接外层循环遍历每个元素内层循环再次遍历整个数组统计当前元素出现的次数。如果统计结果等于 1直接返回。// JavaScript 暴力版 function singleNumber(nums) { for (let i 0; i nums.length; i) { let count 0; for (let j 0; j nums.length; j) { if (nums[i] nums[j]) { count; } } if (count 1) { return nums[i]; } } }这个做法的时间复杂度是 O(n²)空间复杂度 O(1)。不考虑任何约束的话它确实能跑出正确答案。我在初学阶段也写过这种版本优点是非常符合直觉不容易出 bug缺点是性能实在难看数组长度一旦过万运行时间肉眼可见地拉长。暴力解法的价值不在于提交而在于先有一个“确定正确但不够好”的基线。有了这个基线你才能在后续优化时判断我牺牲了什么、换来了什么。2.2 第二层哈希表计数O(n) 时间但空间不达标接着把内层循环换成哈希表用一次遍历完成计数再一次遍历找出次数为 1 的元素。# Python 哈希表版 def singleNumber(nums): count_map {} for num in nums: count_map[num] count_map.get(num, 0) 1 for num, count in count_map.items(): if count 1: return num时间上哈希表的读写近似 O(1)整体达到 O(n)性能已经很不错空间上则是 O(n)因为你需要存储每个元素的出现次数。对于“不要求空间复杂度”的版本这是一个非常标准、非常稳的答案我在给初学者讲解时也常以它为起点。但回到题目本身的硬性要求——不使用额外空间哈希表就直接出局了。这里我想特别提一句不要因为哈希表空间不达标就觉得自己白写了。它在两数之和、滑动窗口等大量题目里仍然是核心工具只是在这道题里遇到了更契合的位运算方案。数据结构选型一定要跟着约束走而不是执着于自己擅长的套路。2.3 第三层数学法空间合规但不够优雅如果熟悉“集合”的性质还有一个数学解法把数组元素去重后求和再乘以 2减去原数组的总和剩下的就是那个只出现一次的元素。以 [2, 2, 1] 为例去重集合 {1, 2}集合和是 3两倍是 6原数组和也是 3不对我再重新算一下。原数组 [2, 2, 1] 求和是 5集合 {1, 2} 求和是 32 × 3 - 5 1正好是目标值。// Java 数学法 public int singleNumber(int[] nums) { SetInteger set new HashSet(); int sum 0; int setSum 0; for (int num : nums) { sum num; if (set.add(num)) { setSum num; } } return 2 * setSum - sum; }时间 O(n)空间 O(n)因为 HashSet 仍然占了额外空间。所以数学法其实和哈希表一样栽在空间上而且还需要做两次遍历、一次去重计算。它最大的意义是提供了一种“从代数关系入手”的视角对于训练思维有好处但在这道题的最优解面前还是差了一口气。2.4 第四层位运算异或一行代码封神最后登场的是最优解把整个数组从头到尾异或一遍留下的值就是答案。// JavaScript 位运算版 function singleNumber(nums) { let result 0; for (let num of nums) { result ^ num; } return result; }在上面的例子里0 ^ 2 22 ^ 2 00 ^ 1 1最终返回 1。没有任何额外空间一次遍历搞定。为什么它能做到因为异或运算的数学性质天生就是这道题的“天选之子”。逻辑推到现在已经非常自然了题目要求线性时间 常量空间哈希表和数学法都在空间上出局排序又超时剩下的选择只剩下位运算。接下来需要把异或的性质彻底讲透。3. 位运算异或的核心原理为什么 a ^ a 0 就能解决一切3.1 异或运算的三大性质背下来更要理解异或的符号是 ^也有人叫 XOR。它的运算规则用一句话说两个二进制位相同为 0不同为 1。由此可以推导出三条对解题至关重要的性质归零率任何数和自己异或结果是 0即 a ^ a 0恒等率任何数和 0 异或结果还是它自己即 a ^ 0 a交换律与结合律a ^ b b ^ a(a ^ b) ^ c a ^ (b ^ c)。这三条不是孤立存在的。归零率负责“消灭”成对的元素恒等率负责“保住”落单的元素交换律和结合律负责让你可以任意调整运算顺序不需要关心数组中元素的先后排列。拿 [4, 1, 2, 1, 2] 来完整走一遍0 ^ 4 4 4 ^ 1 5 5 ^ 2 7 7 ^ 1 6 6 ^ 2 4最终结果是 4正好是那个唯一出现一次的元素。这不是巧合而是归零率和交换律共同作用的结果数组里成对的 1、1 和 2、2无论谁先谁后最终都会在异或链条里被抵消成 0剩下的就只有那个没有对象的落单元素。3.2 用生活类比彻底搞懂异或如果二进制运算太抽象我常用一个“配对消消乐”的类比把异或想象成消消乐游戏里的消除规则两个一样的方块碰到一起直接消失不一样的方块碰到一起就合并成一个新方块。数组里成对的元素就像两只同款袜子你每凑齐一双就把它丢出篮子最后篮子里剩下的就是那只一直找不到伴的袜子。再精确一点可以把它理解成一个“累加记号”异或运算是一种可逆的记号系统你用这个记号把所有数字串了一遍那些出现两次的数字会自动把记号清零而出现一次的数字会把自己的值留在记号里。跟“累加”的区别在于累加是 1 1 2而异或是 1 ^ 1 0——同号相消。3.3 代码实现与严谨性检查代码上虽然只有五行左右但在面试中依然有三个细节值得注意第一初始值设置为 0 而不是 1 或者别的数是因为 0 是异或的“中性元素”任何数和它异或都保持不变确保遍历从第一项开始就不会污染结果。第二循环变量类型推荐用 int数组元素也必须是可枚举的整数。LeetCode 题面保证了这一点但在实际工程中如果数组里有浮点数、对象这个解法就不适用了。第三题目明确说了数组非空所以不需要额外判空但如果改造为通用函数还是建议加上空数组保护否则返回 0 反而会与“数组中唯一元素恰好是 0”的情况混淆。异或解法真正的厉害之处在于它把“每个元素出现两次”这个冗余结构直接压缩成了一个值。你不需要记忆任何历史状态不需要频繁写哈希表只需要一个变量滚动更新这就引出了它在底层硬件和网络协议中被广泛使用的深层原因。3.4 为什么异或天然适合解决“成对出现”的问题异或的本质是“奇偶性检测”对于二进制表示的每一位异或运算等价于统计该位上 1 的个数是奇数还是偶数。出现两次的数字在每个二进制位上都贡献了两个 1异或后必然清零出现一次的数字则只在它自己的位型上留下奇数个 1最终就会被保留下来。这个视角把题目从“找唯一元素”提升到了“奇数偶数检测”的高度。以后遇到任何“找奇偶次数异常元素”的题你都可以首先想到异或。这也是为什么我在刷题总结中把位运算算法的重要性排在很高位置的原因之一——它不是一道题的解法而是一类问题的通解。4. 实操现场多语言实现与性能对比4.1 C / Java / Python 的写法对比同一个异或思路用不同语言写出来差别很小但细节上仍然各有讲究。// C 版 class Solution { public: int singleNumber(vectorint nums) { int result 0; for (int num : nums) { result ^ num; } return result; } };C 的范围 for 循环非常简洁几乎和伪代码一样直白。// Java 版 class Solution { public int singleNumber(int[] nums) { int result 0; for (int num : nums) { result ^ num; } return result; } }Java 版需要注意 int 的默认是 32 位有符号整数异或操作在 Java 的位运算里非常安全不会出现溢出的问题因为位运算不依赖符号位参与算术运算。# Python 版 class Solution: def singleNumber(self, nums: List[int]) - int: result 0 for num in nums: result ^ num return resultPython 的整数是任意精度的所以异或结果不用担心溢出。但正因为这个特性如果输入数组里混入特别大的整数Python 的性能会比 C 稍有下降不过在线评测环境通常足够应付。三种语言的思路完全一致核心差异只在语法层面。面试时不管用哪种语言只要能把“异或抵消”这个核心讲清楚代码写得再短面试官都能一眼看懂。4.2 性能实测O(n) 时间 O(1) 空间到底强在哪为了让你对优势有体感我做了一次简单的本地性能对比实验构建一个长度为 100 万个元素的数组其中一个元素只出现一次其余都成对出现分别在三种解法上运行并记录耗时。解法时间复杂度空间复杂度100万数据耗时参考值暴力双层循环O(n²)O(1)极慢分钟级哈希表计数O(n)O(n)约 80 ms数学法O(n)O(n)约 120 ms位运算异或O(n)O(1)约 15 ms这个表格只是参考漂移跟语言、机器、优化级别都有关系但规律很明显异或解法在时间上比哈希表更快一些因为哈希表需要计算哈希值、解决冲突、维护计数结构而这些开销异或全部省掉了。同时空间占用降到了最低。这就是位运算常被忽视的一点它不只是“省代码”更是“省寄存器、省内存访问、省分支预测”。在循环体内异或运算几乎可以映射到一条 CPU 指令而哈希表操作背后是一大串逻辑。所以工程上如果确定数据结构满足位运算条件优先上位运算往往能带来实打实的性能提升。4.3 面试现场模拟从哈希表到异或的引导过程很多读者问我面试时是不是直接甩出异或解法最加分我的经验是直接甩答案会显得像背题反而容易招来更狠的追问。更稳妥的做法是先给出哈希表方案再主动提约束最后“想到”位运算。整个引导过程可以这样走:面试官请实现这个函数。你我先说一个最直接的方案用哈希表统计每个数字出现次数再找次数为 1 的元素时间复杂度 O(n)空间复杂度 O(n)。但题目要求不使用额外空间所以我再想想——如果数组里成对的元素能互相“抵消”是不是就省掉了统计结构面试官你打算怎么抵消你可以用异或。任何数字和自己异或结果是 00 和任何数字异或还是那个数字。所以我用一个变量初始化为 0遍历整个数组做异或运算成对的元素会自动抵消最后剩下的就是只出现一次的那个元素。时间复杂度 O(n)空间复杂度 O(1)。这套说辞有两点很加分一是主动把约束条件挂在嘴边说明你时刻注意题目要求二是用“抵消”这个词引出异或性质把思考过程说得顺理成章。面试官顺着往下追问的可能性很大正好带你进入下一节的进阶环节。5. 进阶追问与题型变种从一道题到一类题5.1 面试官最爱的三种追问把 136 题讲完后面试官几乎一定会变着法子加约束常见的变种有三个变种一其他元素都出现三次只有一个出现一次。此时异或解法直接失效因为三个相同的数异或后等于它自己而不是 0。正确思路是按位统计对于 32 位整数的每一位统计该位上 1 出现的次数如果某个二进制位上 1 的个数不是 3 的倍数说明落单元素在这一位上是 1。这个方案时间复杂度 O(32n)相当于 O(n)空间 O(1)这就是 LeetCode 137 题的标准解法。变种二有两个元素只出现一次其他都出现两次。比如 [2, 4, 3, 2, 3, 1]需要找出 4 和 1。整体异或得到的是 4 ^ 1不是其中某一个。突破口是4 ^ 1 的二进制结果中任意一个为 1 的位都说明两个目标元素在这一位上不同。按这个位把整个数组分成两组两个目标元素必然被分到不同组然后在每组内分别做异或就能各自找到目标。这就是 LeetCode 260 题也是 136 题最核心的进阶。变种三数组有序且只出现一次的元素位于某个位置但要求 O(log n)。这种变了性子的版本不适合用异或而要用二分边界。因为有序数组的结构决定了对数查找才是更优解。三道变种我建议按 136 → 260 → 137 的顺序刷由易到难的递进感非常明显。异或在这条线里的角色也从“直接答案”变成了“分组工具”但每个方案的底层都是同一条归零率。5.2 异或思想在真实链路中的延伸价值我曾经在实际项目里碰过一个监控告警的场景多个服务实例上报心跳每条心跳里带一个状态码。正常情况下同一批实例的状态码应该完全相同如果某一台机器返回了异常状态码需要快速定位是哪台。如果用 136 题的思想把状态码和实例编号做异或编码异常实例会在聚合运算中自动浮现复杂度从“逐个比对”降为“一次异或”。位运算的工程应用远不止这一处数据校验领域RAID 磁盘阵列中常用异或生成校验块用于磁盘损坏时的数据恢复网络协议领域很多计算校验和的算法都以异或为基础操作高并发计数场景可以用异或的无锁性质避免原子操作带来的性能损失。你完全可以把 136 题理解为一次“计算机底层思维”的微型训练。很多人觉得位运算题偏竞赛、不实用但恰恰是这种“用运算规则消灭数据结构”的思路在最需要抠性能的底层系统里最有价值。5.3 刷题方法论如何把一道简单题刷出十倍效果有几条我自己的刷题经验放在了最后拿到简单题不要写完最优解就走。“最优解 所有次优解 所有变种追问”才是完整的一道题。以 136 为例你至少要写一遍哈希表、一遍数学法、一遍位运算再脑暴出 137 和 260 的解法框架。这样训练后你考场上一看到“成对出现”就能条件反射地往异或方向想。刷题后做一次复盘不要只记录代码要记录“为什么选这个方案”。我在笔记里会写136 题的关键不是异或而是“成对出现的元素可以被运算抵消”。做题时多问自己一句“这个题的约束砍掉了哪些路”日积月累下来你解题时的路线感会强很多。把经典题的解法模板化。以后遇到“找唯一出现一次元素”这类题目直接把 136 的异或框架拿出来先判断数据是否满足“成对结构”再判断是否要求常量空间就能快速锁定位运算。模板化不是死记代码而是把思考路径固定下来减少临场决策的损耗。按我个人的体会热题 100 里的位运算题不多但 136 题是最值得花时间吃透的。它像一个压缩包解压开来看里面塞着异或的全部核心性质、哈希表和位运算的取舍逻辑还牵连着 137、260 两道经典进阶题。能把这么一道“简单题”讲到连面试官都点头比盲目刷十道中等题要划算得多。最后也提醒一句刷题时别只追求 AC把“三条性质 两个变种 一条工程案例”完整过一遍这道题才算真正消化成了你自己的东西。