LeetCode 136. 只出现一次的数字
题目核心
给你一个非空整数数组 nums，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
要求：算法应该具有线性时间复杂度，并且不使用额外空间。
例如：
nums = [2, 2, 1]
答案：1
nums = [4, 1, 2, 1, 2]
答案：4
nums = [1]
答案：1解题思考过程
第一步：理解问题
数组里每个元素要么出现一次，要么出现两次，只有一个例外。要找出那个"落单"的元素。
关键约束：O(n) 时间、O(1) 空间。这就排除了排序（O(n log n)）和哈希表（O(n) 空间）作为最优解。
第二步：暴力解法（哈希表）
最直观的思路：用哈希表统计每个元素出现次数，再遍历哈希表找出现一次的。
时间复杂度：O(n)
空间复杂度：O(n)可行，但不满足 O(1) 空间要求。需要找别的路。
第三步：想到位运算
题目有个关键特征：其他元素都出现两次，只有一个出现一次。"两次"这个条件很特殊，让人联想到能不能让出现两次的元素互相"抵消"掉，剩下的就是答案。
什么运算能让两个相同的数抵消成 0？——异或（XOR）。
第四步：异或的性质
回顾异或的几条关键性质：
1. a ^ a = 0 （任何数和自己异或为 0）
2. a ^ 0 = a （任何数和 0 异或为自身）
3. 异或满足交换律和结合律：a ^ b ^ c = c ^ a ^ b把这三条合起来看：如果对数组所有元素依次异或，出现两次的元素两两配对异或成 0，最后整个异或结果就等于那个只出现一次的元素。
nums = [4, 1, 2, 1, 2]
4 ^ 1 ^ 2 ^ 1 ^ 2
= 4 ^ (1 ^ 1) ^ (2 ^ 2) // 交换律 + 结合律
= 4 ^ 0 ^ 0
= 4完美！出现两次的都被抵消了。
第五步：验证
再试 nums = [2, 2, 1]：
2 ^ 2 ^ 1 = 0 ^ 1 = 1 ✓nums = [1]：
1 ✓（只有一个元素，直接是答案）第六步：复杂度
时间复杂度：O(n) - 遍历一次数组
空间复杂度：O(1) - 只用一个变量满足题目要求，这是最优解法。
当前解法：位运算（异或）
/**
* @param {number[]} nums
* @return {number}
* 位运算
*/
var singleNumber = function (nums) {
let res = nums[0];
for (let i = 1; i < nums.length; i++) {
res ^= nums[i];
}
return res;
};代码逐行解释
初始化结果
let res = nums[0];把第一个元素作为初始结果。等价于 res = 0 ^ nums[0]（0 异或任何数为自身），从第一个元素开始累积异或。
也可以写成 let res = 0; 然后从 i = 0 开始，效果一样。当前写法是少一次异或运算的小优化。
遍历异或
for (let i = 1; i < nums.length; i++) {
res ^= nums[i];
}从第二个元素开始，依次和 res 异或：
res ^= nums[i]等价于res = res ^ nums[i]。- 出现两次的元素会在两次异或中互相抵消（
a ^ a = 0）。 - 只出现一次的那个元素，只被异或一次，最后保留下来。
返回结果
return res;遍历结束后，res 就是那个只出现一次的元素。
执行过程示例
以 nums = [4, 1, 2, 1, 2] 为例：
初始：res = 4
i=1: res = 4 ^ 1 = 5
i=2: res = 5 ^ 2 = 7
i=3: res = 7 ^ 1 = 6
i=4: res = 6 ^ 2 = 4
最终返回 4换一种角度看（利用交换律结合律重新分组）：
4 ^ 1 ^ 2 ^ 1 ^ 2
= 4 ^ (1 ^ 1) ^ (2 ^ 2)
= 4 ^ 0 ^ 0
= 4中间过程的 res 值（5、7、6）看起来没有规律，但最终一定会回到 4，因为两个 1 和两个 2 都被抵消了。
为什么异或能工作
核心在于"出现两次"这个条件正好匹配异或的抵消性质：
| 异或性质 | 作用 |
|---|---|
a ^ a = 0 | 出现两次的元素互相抵消 |
a ^ 0 = a | 只出现一次的元素保留下来 |
| 交换律、结合律 | 异或顺序无关，可以任意分组 |
如果题目改成"其他元素出现三次"，异或就不管用了（需要用数位统计的方法）。
复杂度分析
- 时间复杂度：
O(n)。遍历数组一次，每次异或 O(1)。 - 空间复杂度：
O(1)。只用了一个res变量。
替代解法一：哈希表
用哈希表统计出现次数，找出现一次的元素。
var singleNumber = function (nums) {
const count = new Map();
for (const num of nums) {
count.set(num, (count.get(num) || 0) + 1);
}
for (const [num, c] of count) {
if (c === 1) return num;
}
};- 时间复杂度：
O(n) - 空间复杂度：
O(n)
思路直观，但不满足 O(1) 空间要求。
替代解法二：排序后比较相邻
排序后，相同元素相邻，比较 nums[i] 和 nums[i+1]：
var singleNumber = function (nums) {
nums.sort((a, b) => a - b);
for (let i = 0; i < nums.length; i += 2) {
if (nums[i] !== nums[i + 1]) {
return nums[i];
}
}
return nums[nums.length - 1];
};- 时间复杂度：
O(n log n)（排序） - 空间复杂度：取决于排序实现
效率最低，仅作思路参考。
三种解法对比
| 解法 | 时间复杂度 | 空间复杂度 | 特点 |
|---|---|---|---|
| 位运算（异或） | O(n) | O(1) | 最优解，巧妙利用异或抵消 |
| 哈希表 | O(n) | O(n) | 思路直观，空间不达标 |
| 排序 | O(n log n) | 取决于实现 | 时间空间都不达标 |
面试中优先写异或解法，它简洁高效，且体现了对位运算的理解。
易错点
不要忘了初始值：
res = nums[0]对应循环从i = 1开始；如果res = 0则从i = 0开始。两者等价，别搞错循环起点。异或不是加减：
res ^= nums[i]是位运算，不是res -= nums[i]。别用加减去"抵消"，那只在某些特殊情况凑巧成立。适用条件：异或法只适用于"其他元素出现偶数次"的情况。如果改成出现 3 次，需要换思路（按位统计 1 的个数对 3 取模）。