1. 为什么我把LeetCode 136单独拎出来写一篇1.1 题目到底在问什么LeetCode第136题“只出现一次的数字”是我刷题过程中印象很深的一道题。题目描述非常简短给定一个非空整数数组 nums除了某个元素只出现一次以外其余每个元素均出现两次。找出那个只出现了一次的元素。要求实现线性时间复杂度的解决方案并且不使用额外空间。说白了就是给一个数组里面所有数字都是成对出现的唯独有一个“落单”的数字你要把它找出来。比如[2, 2, 1]结果是 1再比如[4, 1, 2, 1, 2]结果应该是 4因为 1 和 2 都出现了两次只有 4 出现了一次。1.2 这题被低估在哪里我第一次做这道题的时候脑子里全是哈希表。遍历一遍统计每个数字出现的次数最后把出现次数为 1 的那个数字返回完事。提交之后确实过了但后来在一次模拟面试中被打了个措手不及。对方问我你能不能用 O(1) 的空间复杂度解决我当场愣住。这也是我把这题专门拎出来写一篇的原因。它表面上是一道“简单题”但它真正想考察的不是“你会不会用哈希表”而是“你有没有意识到位运算的存在”。哈希表解法人人都能写出来但能在不申请额外空间的前提下用 O(n) 时间跑完这道题的人才算真正理解它背后的东西。这题在算法面试中的地位很特别。它是很多公司考察候选人对基础运算理解深度的试金石也是位运算专题里最常见的入门题。如果你只背住了答案没有理解异或的核心性质面试官只要追问一句“为什么异或能找出唯一数字”很多人就露馅了。所以我建议每个刷题的人都不要放过这道题。2. 哈希表、排序这些常规解法的性能账2.1 哈希表计数最符合直觉但空间超标先说我一开始想到的做法。用哈希表统计每个元素出现的次数然后遍历哈希表找到值为 1 的那个键。class Solution: def singleNumber(self, nums: List[int]) - int: count {} for num in nums: count[num] count.get(num, 0) 1 for key, value in count.items(): if value 1: return key这个解法的时间复杂度是 O(n)因为遍历了两遍数组每遍都是线性的。但空间复杂度是 O(n)因为哈希表要存下每一个不同的数字。如果数组里有 n/2 个不同的数字哈希表就得占用 O(n/2) 的空间。题目要求“不使用额外空间”哈希表明显不合格。很多人会忽略这一点因为LeetCode原题描述里“不使用额外空间”是写在进阶要求里的。但面试中面试官往往会直接把它当成硬性条件来问。2.2 排序法代码短但时间上就被淘汰了还有一个思路是先排序再检查相邻元素。因为相同的数字都出现过两次排序之后它们一定会紧挨在一起。只需要从前往后遍历遇到某个元素和它后面的元素不一样那它就是答案。class Solution: def singleNumber(self, nums: List[int]) - int: nums.sort() for i in range(0, len(nums) - 1, 2): if nums[i] ! nums[i 1]: return nums[i] return nums[-1]这个解法的代码非常短也很好理解。但问题在于排序本身的时间复杂度是 O(n log n)已经超出了题目要求的“线性时间复杂度”。如果数组有 10 万个元素排序就比线性遍历多花大约 17 倍的时间这个差距在数据量变大之后非常明显。2.3 三种解法对比解法时间复杂度空间复杂度是否满足题目要求双重循环暴力比较O(n²)O(1)否时间严重超标哈希表计数O(n)O(n)否空间不满足排序后检查相邻元素O(n log n)O(1)部分语言排序会占用额外栈空间否时间不满足异或运算O(n)O(1)完全满足从表格里能清楚看到前三种解法都有明显的短板。要么时间不达标要么空间超标只有异或运算在时间和空间上都满足要求。这也是为什么这道题被归类到“位运算”专题它考察的从来不是容器操作而是对异或特性的理解。3. 异或运算的三条性质与“配对消消乐”模型3.1 三条必须刻进脑子里的性质异或XOR是位运算里最神奇的一个运算符符号是^。它做的事情是把两个数字转换成二进制然后逐位比较相同为 0不同为 1。举个例子5 ^ 3101 011 ----- 110结果是 110也就是十进制的 6。异或有三个核心性质这道题全靠它们归零律x ^ x 0。任何数字和自己异或结果都是 0。因为每一位都是相同的按位比较全部相同所以每一位都变成 0。恒等律x ^ 0 x。任何数字和 0 异或结果都是它自己。因为 0 的每一位都是 0和二进制位做异或时0 ^ 0 01 ^ 0 1完全不变。交换律和结合律a ^ b ^ c a ^ c ^ b (a ^ b) ^ c。异或运算不在乎计算顺序你可以按照任意顺序进行异或。归零律解决“成对数字”的问题恒等律解决“落单数字保留”的问题交换律和结合律保证“乱序计算也不影响结果”。这三条性质拼在一起就是这道题的完整解。3.2 用一个生活化模型理解配对消消乐我给学生讲这题的时候喜欢用一个比喻把异或想象成一个自动消消乐游戏。规则很简单两个一模一样的数字碰到一起互相抵消变成 0 消失。0 什么都不碰谁遇到它都不受影响。数字之间玩消消乐的时候不管按什么顺序碰结果都一样。回到题目本身。数组里的数字都是一个一个的玩家除了那个“落单”的数字外其余每个数字都有另一个和自己完全一样的“双胞胎”。所有双胞胎在异或游戏里都两两抵消了变成一串 0 留在场上。这个时候“落单”的数字遇见 0按照恒等律它保持原样。所以全部异或完还剩下的那个值就是我们要找的答案。3.3 手动演算两个例子第一个例子[2, 2, 1]0 ^ 2 2 2 ^ 2 0 0 ^ 1 1答案是 1。第二个例子[4, 1, 2, 1, 2]0 ^ 4 4 4 ^ 1 5 5 ^ 2 7 7 ^ 1 6 6 ^ 2 4答案是 4。再看一遍二进制层面的过程会更直观。拿[4, 1, 2, 1, 2]举例这些数字的二进制分别是4 100 1 001 2 010 1 001 2 010从左到右异或100 ^ 001 101 101 ^ 010 111 111 ^ 001 110 110 ^ 010 100 // 结果回到 4你可以看到1 和 2 都出现过两次它们对应的二进制位在异或过程中被完全抵消最终剩下的就是没有“对手”的 4。整个过程不需要额外数组不需要标记任何状态只需要一个变量从头滚到尾。4. 代码落地C、Python、JavaScript的写法和细节4.1 最朴素的循环写法理论讲清楚了代码反而是最简单的一步。核心逻辑只需要三行初始化一个变量为 0遍历数组不断异或最后返回结果。class Solution { public: int singleNumber(vectorint nums) { int ans 0; for (int num : nums) { ans ^ num; } return ans; } };class Solution: def singleNumber(self, nums: List[int]) - int: ans 0 for num in nums: ans ^ num return ansclass Solution { public int singleNumber(int[] nums) { int ans 0; for (int num : nums) { ans ^ num; } return ans; } }var singleNumber function(nums) { let ans 0; for (const num of nums) { ans ^ num; } return ans; };这四种写法思路完全一致没有任何区别。时间复杂度 O(n)空间复杂度 O(1)。4.2 一行写法与函数式风格如果你熟悉函数式编程Python和JavaScript都可以用reduce一行搞定。from functools import reduce from operator import xor class Solution: def singleNumber(self, nums: List[int]) - int: return reduce(xor, nums)注意这里不能直接用reduce(lambda x, y: x ^ y, nums)吗也可以但operator.xor比 lambda 稍微快一点也更规范。var singleNumber function(nums) { return nums.reduce((acc, num) acc ^ num, 0); };JavaScript的reduce第二个参数是初始值传 0 进去语义上就变成了“从 0 开始异或所有数字”。4.3 初始值选 0 还是选第一个元素很多教程里会写ans nums[0]然后从i 1开始遍历。这样写也能得出正确答案因为nums[0] ^ nums[0] 0最后剩下的依然是落单者。但我更推荐从 0 开始异或原因有两个。第一代码更简洁不需要特判数组下标。第二更健壮即使输入是空数组返回值也是 0不会出现越界错误。LeetCode 题目保证数组非空从工程习惯的角度看从 0 开始的写法更统一、更不容易出错。还有一个小细节LeetCode 的输入类型是List[int]、vectorint这类整数数组里面可能会有零也可能有负数。异或运算对符号位一视同仁负数的补码表示下x ^ x 0依然成立。这点在后面的边界条件章节里再展开说。5. 边界条件与调试负数、零、只有一个元素的三种情况5.1 数组只有一个元素如果nums [5]代码从 0 开始0 ^ 5 5直接返回 5。这个用例看起来简单但很容易被人忽略。有些解法如果用了“先排序再比较相邻元素”的逻辑数组长度为 1 时可能因为访问nums[1]而越界。异或解法天然免疫这种情况。5.2 负数参与异或有人会担心异或对负数有效果吗答案是有效而且非常自然。计算机里的负数是以补码形式存储的。比如 -1 在 32 位系统中表示为全 111111111111111111111111111111111。两个 -1 异或每一位都相同结果每一位都是 0最终得到 0。试一下数组[-1, -1, 2]0 ^ (-1) -1 (-1) ^ (-1) 0 0 ^ 2 2答案是 2完全正确。所以根本不需要对负数做任何特殊处理。5.3 数据范围影响在 C 或 Java 中int类型是 32 位的如果数组里的数字比较大比如接近INT_MAX异或结果会不会溢出这里有个非常重要的知识点异或运算不涉及进位它只是逐位比较。加法运算会因为进位导致溢出但异或运算每一位都是独立的最高位的 1 和 0 做异或结果还是 1 或 0不会产生进位因此不存在“溢出”的概念。用生活类比就是加法像两个人搬运货物进位就是货物太多需要借位到下一车而异或只是简单核对清单每一位都独立工作谁也不影响谁。所以用int类型保存异或中间值是绝对安全的。5.4 我踩过的坑把题目条件记反早期我写过一种自以为聪明的写法先把数组排序然后每隔两个比较一次。逻辑是对的但我在比较时用了nums[i] ! nums[i 1]当i走到倒数第二位时如果它是答案下一次比较就会访问越界。我当时调试了很久才发现问题。最后还是回到异或解法彻底避开了这一类下标问题。另一个坑是误以为“出现两次”意味着“所有数字都出现偶数次”所以在遍历时自作主张做了去重处理。实际上题目只保证“除落单者外其余数字出现两次”并不会出现“某个数字出现 4 次”的情况。如果你自己的代码里加了过于复杂的判断反而可能误伤正确输入。5.5 推荐的穷尽测试用例调试时用下面这组用例基本能把常见问题全部覆盖输入数组预期输出[1]1[1, 1, 2]2[2, 2, 1]1[-1, -1, 2]2[0, 1, 1]0[4, 1, 2, 1, 2]4[300, 300, -100]-100这里面包含了一个元素、负数、零、交替顺序等情况。异或解法在所有这些用例下都能稳定输出正确结果。6. 从136长出去的位运算题目群两次、三次、缺失6.1 从“一次”到“两次”两个落单数字的情况LeetCode 136的常见变形是第260题“只出现一次的数字 III”。题目改为数组里有两个数字只出现一次其余数字都出现两次找出这两个数字。思路也很漂亮。先把所有数字异或一遍得到diff a ^ b其中 a 和 b 是那两个落单的数字。因为 a 和 b 不同所以diff中至少有一位是 1。找到最低位的 1记为mask。这一位在 a 和 b 中必然一个是 1另一个是 0。接着用mask把数组分成两组这一位是 1 的一组这一位是 0 的一组。这样 a 和 b 就被分开了每组内部再各自异或就能得到最终答案。关键步骤是找到最低位的 1int mask diff (-diff);不写太多代码但这道题的核心思路值得在面试中展示因为它体现了异或“分组”的威力。6.2 从“两次”到“三次”异或失效了怎么办如果题目改成“只有一个数字出现一次其余数字都出现三次”异或就失效了。因为x ^ x ^ x x三次异或的结果不等于要把这个数消掉。这时候要用按位统计的思路把每个数字的二进制位拆开逐位统计每个位置上 1 出现的次数。出现三次的数字其每个二进制位上 1 的个数一定是 3 的倍数。对 3 取模之后剩下的就是那个落单数字在该位上的值。class Solution { public: int singleNumber(vectorint nums) { int ans 0; for (int bit 0; bit 32; bit) { int cnt 0; for (int num : nums) { if ((num bit) 1) { cnt; } } if (cnt % 3 ! 0) { ans | (1 bit); } } return ans; } };这种解法的时间复杂度是 O(32n)虽然常数比较大但依然是线性的空间 O(1)。它是异或解法的重要补充也是面试中区分“只会背答案”和“真正理解位运算”的经典题目。6.3 缺失数字异或解决索引与值的配对再往外延伸一步LeetCode 268“丢失的数字”。题目给一个包含 0 到 n 中 n 个数字的数组找出缺失的那个。除了求和公式外异或也能做。思路是把数组所有元素和 0 到 n 的所有整数全部异或起来。数组中的每个数字都在 0 到 n 之间所以成对的数字全部抵消剩下的一定是缺失的那个。class Solution: def missingNumber(self, nums: List[int]) - int: ans 0 for i, num in enumerate(nums): ans ^ i ans ^ num ans ^ len(nums) return ans这里把数组下标和元素值配对异或正好凑成“完整集合”和“缺失集合”的差集。这种利用索引和值配对的思路也是位运算题目里非常经典的套路。6.4 面试中的加分表达我把136这道题练熟之后在面试里被追问过很多次。面试官常见的追问顺序是能不能不用哈希表——引出异或。为什么异或能正确找到落单数字——引出三条性质。如果出现两次的数字不止一个呢——引出分组异或。如果改成出现三次呢——引出按位取模。如果数字范围是 1 到 n 且缺失一个呢——引出索引配对。把这五层准备齐全一道简单题就能撑起一次有深度的算法面试。我曾用这个答题框架在一次模拟面试中被评价为“基础扎实”因为大多数候选人只能答到第二层很少有人能主动把后面的变形题串起来讲。6.5 我个人的学习和复习建议说点实际的。136这道题我建议你用三种方式各写一遍手写循环、函数式一行、甚至用纸笔手动演算几组二进制数据。第一次刷题的人往往只满足于“代码能跑通”但这道题的精髓在于逻辑链的完整性。我的习惯是每做完一道位运算题目就在笔记里画一张思维导图记录“它用了异或哪条性质”“它和其他题目的联系是什么”“如果条件改变了我该往哪个方向思考”。时间久了你会发现位运算题目从来不是一道一道孤立存在的它们是一张互相连接的网。136就是这张网的一个锚点把它吃透了后面的260、137、268都能轻松带出来。这也是为什么我建议所有刷题的人不要在 AC 之后就急着做下一道题多花十分钟把题目的性质、边界、变形想清楚。这十分钟省下来的可能是之后若干道位运算题目的学习时间。