136. 只出现一次的数字
难度：简单 | 主题：数组、位运算
题目
给你一个非空整数数组 nums，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。要求实现线性时间复杂度的解法，且不使用额外空间。
示例
输入：nums = [2,2,1]
输出：1
思路
先讲个故事：找落单的人
公司团建，所有人两两配对合影。突然发现有一个人落单了——没人跟他合照。你不会逐个问”你跟谁拍的”——你让所有人两两握手，配成对的就消掉了，最后剩下的那个就是落单的。
这就是异或运算：a ^ a = 0（成对消掉），a ^ 0 = a（落单保留）。
引导式推导：异或的魔法
把所有数异或一遍，出现两次的全抵消为 0，剩下的就是只出现一次的数。
graph LR A["全部异或"] --> B["a ^ a = 0<br/>成对消掉"] B --> C["0 ^ x = x<br/>落单保留"] C --> D["结果 = 只出现一次的数"]
| 方法 | 时间 | 空间 |
|---|---|---|
| 异或 | O(n) | O(1) |
| 哈希表 | O(n) | O(n) |
| 排序 | O(n log n) | O(1) |
代码
def singleNumber(self, nums):
res = 0
for num in nums:
res ^= num
return res
一行版：reduce(lambda x, y: x ^ y, nums)
复杂度
| 指标 | 值 | 解释 |
|---|---|---|
| 时间 | O(n) | 遍历一次数组 |
| 空间 | O(1) | 只用一个变量 |
实战考量
频率分析
出现在：位运算经典题。常见，是位运算类题目的入门必会。几乎所有公司一面都会考。
延伸思考
Q：为什么异或能找出单身元素？
A：异或本质是「无进位加法」，检测奇偶次出现。a ^ a = 0（成对抵消），a ^ 0 = a（单身保留）。交换律和结合律保证顺序不影响结果。
Q：如果两个元素出现一次，其他出现两次呢？（260 题）
A：全部异或后得到 x ^ y（两个单身元素的异或）。取 x ^ y 的最低位 1 作为分组标志，将数组分成两组分别异或，每组得到各自的单身元素。
Q：如果一个元素出现一次，其他出现三次呢？（137 题）
A：用「三进制」思想，统计每个二进制位出现的次数，模 3 取余后拼成结果。
Q：异或运算有哪些性质？
A：① a ^ a = 0（自反性）；② a ^ 0 = a（恒等性）；③ 交换律；④ 结合律。
易错点
-
res初始化为 0 不是 None -
一行
reduce(lambda x, y: x ^ y, nums)实践中不如循环直观
生活类比
异或消对 → 两人互相抵消
想象一个房间里每个人都有一个双胞胎，大家互相找配对。找到双胞胎的两人一起离开房间。最后剩下来的那个人——就是没有双胞胎的落单者。异或运算就是这个”配对消消乐”的数学版本。
相关题目
| 题目 | 关系 |
|---|---|
| 268丢失的数字 | 同族异或应用 |
| 287寻找重复数 | 位运算 + 快慢指针 |
| 202快乐数 | 数学类 |
→ 返回题单：LeetCode学习路线图 > 十四、数学与位运算
速记卡（面试闪卡）
Q1：一句话讲清「136. 只出现一次的数字」到底是什么？
A：只出现一次的数字，是其余都成对、唯独一个落单，用异或一遍扫就揪出来。
Q2：题目与直觉 —— 怎么理解？
A：数组里除一个元素外其余都出现两次，线性时间、不用额外空间找出它。就像公司团建两两合影，最后没配对、落单的那个人就是答案（single number）。
Q3：核心思路——异或消对 —— 怎么理解？
A：把所有数异或一遍，出现两次的全抵消为 0，只剩落单的。好比房间里每人找双胞胎，配成对的拉走，剩下来的就是没双胞胎的（XOR）。
Q4：异或的魔法性质 —— 怎么理解？
A：a^a=0（自反）、a^0=a（恒等），再加交换律结合律，顺序随便排。异或是”无进位加法”，专治奇偶次出现（bitwise XOR）。
Q5：复杂度与变体 —— 怎么理解？
A：时间 O(n) 一遍过，空间 O(1) 只用一个变量。进阶：两个落单用最低位 1 分组，三个落单用三进制统计（time/space complexity）。
Q6：核心速记主线有哪些？
-
本质：异或 a^a=0 成对消，a^0=a 落单留
-
写法：res 初始 0，循环 res ^= num
-
进阶：两落单按最低位 1 分组再异或
-
复杂度：时间 O(n)，空间 O(1)
口诀
A：团建合影找落单，异或消对剩自己；
a^a 归零 a^0 留，无进位加显神技；
一遍扫过 O(n) 快，不占内存省力气；
两个单身分组破，三进统计也破题。