企业官网建设流程全解析

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 三种解法对比

从表格里能清楚看到，前三种解法都有明显的短板。要么时间不达标，要么空间超标，只有异或运算在时间和空间上都满足要求。这也是为什么这道题被归类到“位运算”专题，它考察的从来不是容器操作，而是对异或特性的理解。

3. 异或运算的三条性质与“配对消消乐”模型

3.1 三条必须刻进脑子里的性质

异或（XOR）是位运算里最神奇的一个运算符，符号是^。它做的事情是：把两个数字转换成二进制，然后逐位比较，相同为 0，不同为 1。

举个例子，5 ^ 3：

101 011 ----- 110

结果是 110，也就是十进制的 6。

异或有三个核心性质，这道题全靠它们：

1. 归零律：x ^ x = 0。任何数字和自己异或，结果都是 0。因为每一位都是相同的，按位比较全部相同，所以每一位都变成 0。
2. 恒等律：x ^ 0 = x。任何数字和 0 异或，结果都是它自己。因为 0 的每一位都是 0，和二进制位做异或时，0 ^ 0 = 0，1 ^ 0 = 1，完全不变。
3. 交换律和结合律：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(vector<int>& 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 ans

class 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]、vector<int>这类整数数组，里面可能会有零，也可能有负数。异或运算对符号位一视同仁，负数的补码表示下，x ^ x = 0依然成立。这点在后面的边界条件章节里再展开说。

5. 边界条件与调试：负数、零、只有一个元素的三种情况

5.1 数组只有一个元素

如果nums = [5]，代码从 0 开始，0 ^ 5 = 5，直接返回 5。这个用例看起来简单，但很容易被人忽略。有些解法如果用了“先排序再比较相邻元素”的逻辑，数组长度为 1 时可能因为访问nums[1]而越界。异或解法天然免疫这种情况。

5.2 负数参与异或

有人会担心，异或对负数有效果吗？答案是有效，而且非常自然。计算机里的负数是以补码形式存储的。比如 -1 在 32 位系统中表示为全 1（11111111111111111111111111111111）。两个 -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 推荐的穷尽测试用例

调试时用下面这组用例基本能把常见问题全部覆盖：

这里面包含了一个元素、负数、零、交替顺序等情况。异或解法在所有这些用例下都能稳定输出正确结果。

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 就被分开了，每组内部再各自异或，就能得到最终答案。

关键步骤是找到最低位的 1：

int mask = diff & (-diff);

不写太多代码，但这道题的核心思路值得在面试中展示，因为它体现了异或“分组”的威力。

6.2 从“两次”到“三次”：异或失效了怎么办

如果题目改成“只有一个数字出现一次，其余数字都出现三次”，异或就失效了。因为x ^ x ^ x = x，三次异或的结果不等于要把这个数消掉。

这时候要用按位统计的思路：把每个数字的二进制位拆开，逐位统计每个位置上 1 出现的次数。出现三次的数字，其每个二进制位上 1 的个数一定是 3 的倍数。对 3 取模之后，剩下的就是那个落单数字在该位上的值。

class Solution { public: int singleNumber(vector<int>& 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. 能不能不用哈希表？——引出异或。
2. 为什么异或能正确找到落单数字？——引出三条性质。
3. 如果出现两次的数字不止一个呢？——引出分组异或。
4. 如果改成出现三次呢？——引出按位取模。
5. 如果数字范围是 1 到 n 且缺失一个呢？——引出索引配对。

把这五层准备齐全，一道简单题就能撑起一次有深度的算法面试。我曾用这个答题框架在一次模拟面试中被评价为“基础扎实”，因为大多数候选人只能答到第二层，很少有人能主动把后面的变形题串起来讲。

6.5 我个人的学习和复习建议

说点实际的。136这道题，我建议你用三种方式各写一遍：手写循环、函数式一行、甚至用纸笔手动演算几组二进制数据。第一次刷题的人，往往只满足于“代码能跑通”，但这道题的精髓在于逻辑链的完整性。

我的习惯是：每做完一道位运算题目，就在笔记里画一张思维导图，记录“它用了异或哪条性质”“它和其他题目的联系是什么”“如果条件改变了，我该往哪个方向思考”。时间久了，你会发现位运算题目从来不是一道一道孤立存在的，它们是一张互相连接的网。136就是这张网的一个锚点，把它吃透了，后面的260、137、268都能轻松带出来。

这也是为什么我建议所有刷题的人，不要在 AC 之后就急着做下一道题，多花十分钟把题目的性质、边界、变形想清楚。这十分钟省下来的，可能是之后若干道位运算题目的学习时间。