136. 只出现一次的数字 (Easy)
专题归类： 12-技巧 LeetCode 链接： https://leetcode.cn/problems/single-number/
在线做题： 写 Python 代码并运行 · Java 跳转 LeetCode
题目描述
给你一个非空整数数组 nums，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现一次的元素。
你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。
示例 1：
输入：nums = [2,2,1]
输出：1
示例 2：
输入：nums = [4,1,2,1,2]
输出：4
示例 3：
输入：nums = [1]
输出：1
题目详细分析
数据范围： 1 <= nums.length <= 3 * 10^4，-3 * 10^4 <= nums[i] <= 3 * 10^4
核心约束：
- 除一个元素外，其他元素均恰好出现两次——这是关键性质
- 必须 O(n) 时间 + O(1) 空间，排除了哈希表/排序等方案
- 元素可能为负数
关键洞察：
- 题目对时间和空间有严格要求，暗示需要一个数学/位运算技巧
- “出现两次”和”只出现一次”——这个描述强烈暗示**异或（XOR）**运算
- 异或的性质：
a ^ a = 0，a ^ 0 = a，且异或满足交换律和结合律 - 将所有数字异或，成对出现的会抵消为 0，剩下的就是答案
小白版直白理解
就像在一个派对上，大家都成双成对地跳舞，只有一个人是单身。你想快速找出那个单身的人。
最笨的办法是拿个名单，每个人来了就记一笔，最后看谁只出现一次——但这需要额外记名单（哈希表）。
有一个聪明的方法：想象每个数字是一盏灯，碰见相同的数字两次，灯就熄灭（归零）。那么从头到尾把所有数字过一遍，相同的数字会互相抵消，最后剩下的就是那个单身汉。这就像”连连看”的消除游戏——相同的两个碰到一起就消失，最后剩下的就是答案。
解题思路
思路一：异或运算（推荐）
思路讲解： 利用异或运算的三个性质：
a ^ a = 0— 相同数字异或结果为 0（自反性）a ^ 0 = a— 任何数与 0 异或等于自身- 异或满足交换律和结合律：
a ^ b ^ c = a ^ c ^ b
因此，把所有数字异或起来：成对出现的数字异或结果为 0，0 再与单身的那个数字异或，结果就是它本身。
def singleNumber(nums):
ans = 0
for num in nums:
ans ^= num # 所有数异或，成对的消为 0，剩下的就是答案
return ans时间复杂度： O(n) | 空间复杂度： O(1)
思路二：数学法（集合运算）
思路讲解： 如果时间要求不那么严格，可以用数学技巧：2 * sum(set(nums)) - sum(nums)。将所有不同元素的和乘以 2，减去实际数组的和，差就是只出现一次的元素。这需要 O(n) 额外空间存储集合。
def singleNumber(nums):
return 2 * sum(set(nums)) - sum(nums)时间复杂度： O(n) | 空间复杂度： O(n)
思路三：哈希表计数
思路讲解： 用哈希表统计每个数字出现的次数，再找出出现次数为 1 的数字。虽然直观，但不符合 O(1) 空间要求。
def singleNumber(nums):
count = {}
for num in nums:
count[num] = count.get(num, 0) + 1
for num, cnt in count.items():
if cnt == 1:
return num时间复杂度： O(n) | 空间复杂度： O(n)
易错点
- 只有一个元素：如
nums = [1]，异或结果为 1，代码应正确处理 - 负数的情况：异或运算在 Python 中对负数也能正常工作，无需特殊处理
- 不要忘记初始化
ans = 0：如果初始化为其他值，结果会出错 - 异或运算在 Python 中优先级低于比较运算符：如果混合使用需要加括号，但本题中只需连续异或，无需担心
sum(set(nums))可能溢出：虽然 Python 整数无上限，但其他语言需要注意- 题目保证只有 1 个单身数：如果有多个或没有，异或法就不适用了
框架提炼
异或技巧模板：找出现奇数次的元素
def findOdd(nums):
ans = 0
for num in nums:
ans ^= num
return ans核心原理： 异或运算具有自反性（a ^ a = 0），适合解决”配对消除”类问题。
扩展应用：
- 找出现奇数次的数字（不一定是 1 次，3 次、5 次等奇数次都能用异或解决）
- 交换两个数：
a ^= b; b ^= a; a ^= b - 找两个只出现一次的数（见 260 题）：先整体异或得到
x ^ y，再根据某一位分组 - 判断一个数是不是 2 的幂：
n > 0 and (n & (n - 1)) == 0
位运算常用技巧：
| 运算 | 效果 |
|---|---|
x ^ x | 0 |
x ^ 0 | x |
x & (-x) | 取最低位的 1 |
x & (x - 1) | 消除最低位的 1 |
关联题目
- 137-只出现一次的数字II — 每个元素出现三次，只有一个出现一次。用位运算按位统计后 mod 3
- 260-只出现一次的数字III — 有两个只出现一次的数，其他出现两次。整体异或后分组
- 268-丢失的数字 — 异或法找缺失的数字，
0..n全部异或再异或数组元素 - 371-两整数之和 — 用异或和位运算实现加法，不借助
+/-