Single Number 是 LeetCode Hot 100 里面一道非常经典的数组题。
这道题本身不难，甚至看完题目以后，大部分人第一反应都会想到：
“统计每个数字出现的次数，再找出只出现一次的那个数。”
这个思路完全没问题，也很容易写出来。
不过这道题真正有意思的地方在于：
它还有一种更巧妙、更高效的做法——位运算中的异或。
你给出的这两种 Java 代码，正好分别对应了这道题最常见的两类解法：
-
哈希表统计次数
-
异或运算消除重复元素
本文就结合这两种写法，系统地讲一下这道题的思路。
题目介绍
给你一个非空整数数组 nums，除了某个元素只出现一次以外，其余每个元素都恰好出现两次。
要求你找出那个只出现一次的元素。
例如：
nums = [2,2,1]
输出：
1
再比如：
nums = [4,1,2,1,2]
输出：
4
题目还有一个很重要的隐含信息：
-
只有一个元素出现一次
-
其他所有元素都出现两次
这个条件决定了异或解法为什么可行。
示例
示例 1
输入：nums = [2,2,1]
输出：1
因为 2 出现了两次，会被“抵消”，最后剩下的就是 1。
示例 2
输入：nums = [4,1,2,1,2]
输出：4
数组中：
-
1出现两次 -
2出现两次 -
4只出现一次
所以答案就是 4。
示例 3
输入：nums = [1]
输出：1
数组中只有一个元素时，它本身就是答案。
先从最直接的思路开始：哈希表统计次数
很多数组题在第一次做的时候，最容易想到的就是“统计出现次数”。
这道题也一样。
思路
我们可以用一个 HashMap<Integer, Integer> 来记录每个数字出现了几次：
-
遍历数组
-
如果当前数字第一次出现，就记为
1 -
如果已经出现过，就把次数加一
-
最后再遍历一遍
map，找到次数为1的那个数字返回
这个思路非常直观，几乎不需要额外技巧。
代码
class Solution {
public int singleNumber(int[] nums) {
Map<Integer, Integer> map = new HashMap<>();
for (Integer i : nums) {
Integer count = map.get(i);
count = count == null ? 1 : ++count;
map.put(i, count);
}
for (Integer i : map.keySet()) {
Integer count = map.get(i);
if (count == 1) {
return i;
}
}
return -1;
}
}
执行过程分析
假设：
nums = [4,1,2,1,2]
遍历后，map 中保存的数据大概是：
4 -> 1
1 -> 2
2 -> 2
接着再遍历 map：
-
4的次数是1 -
所以直接返回
4
这种写法的优点
-
容易理解
-
容易写出来
-
适合刚开始接触这类题时使用
这种写法的缺点
它虽然好理解，但会使用额外空间。
因为 HashMap 需要把数组中的元素及其出现次数都存下来，所以空间复杂度不会低。
更高效的思路：异或运算
这道题真正的经典解法，是使用异或。
先认识异或的几个性质
异或运算符是 ^。
它有几个非常重要的性质：
-
相同的数异或等于 0
a ^ a = 0
-
任何数和 0 异或都等于它本身
a ^ 0 = a
-
异或运算满足交换律和结合律
也就是说：
a ^ b ^ a = (a ^ a) ^ b = 0 ^ b = b
这个性质一出来，其实就已经很接近答案了。
为什么这道题可以用异或？
因为题目说得非常明确：
-
除了一个数字只出现一次
-
其他数字都出现两次
那么如果我们把整个数组所有元素全部异或起来：
-
成对出现的数字都会变成
0 -
最后剩下的，就是那个只出现一次的数字
例如：
[4,1,2,1,2]
异或过程可以理解为：
4 ^ 1 ^ 2 ^ 1 ^ 2
= 4 ^ (1 ^ 1) ^ (2 ^ 2)
= 4 ^ 0 ^ 0
= 4
所以最终结果就是 4。
异或解法代码
class Solution {
public int singleNumber(int[] nums) {
int res = 0;
for (int num : nums) {
res ^= num;
}
return res;
}
}
代码解释
定义一个变量：
int res = 0;
然后遍历数组，把每个数字都和 res 做异或：
res ^= num;
由于重复的数字会互相抵消，最后 res 中剩下的就是目标值。
执行过程演示
还是以：
nums = [4,1,2,1,2]
为例。
初始时：
res = 0
依次异或：
res = 0 ^ 4 = 4
res = 4 ^ 1 = 5
res = 5 ^ 2 = 7
res = 7 ^ 1 = 6
res = 6 ^ 2 = 4
最后得到：
res = 4
这就是答案。
两种解法对比
方法一：哈希表
思路： 统计每个数字出现的次数，然后返回次数为 1 的数字。
时间复杂度：
O(n)
因为需要遍历数组一次统计次数，再遍历哈希表一次找答案，总体仍然是线性级别。
空间复杂度：
O(n)
因为最坏情况下需要用哈希表存储所有不同的数字。
方法二：异或
思路： 利用异或“相同为 0、和 0 异或得本身”的性质，把所有数字异或起来。
时间复杂度：
O(n)
只需要遍历一次数组。
空间复杂度：
O(1)
只用了一个额外变量 res。
哪种更推荐？
如果只是为了把题做出来，哈希表解法已经足够。
但如果是从面试、算法优化或者 LeetCode 官方标准解法的角度来看，异或解法显然更值得掌握，因为：
-
写法更简洁
-
不需要额外哈希表
-
空间复杂度更优
-
充分利用了题目“其余元素都出现两次”的条件
所以这道题最推荐的做法就是：
遍历数组，整体异或。
为什么异或解法不会出错？
很多人在第一次看到异或做法时，会觉得这种方法“很巧”，但又担心它是不是只是碰巧有效。
其实不是。
它成立的根本原因，是因为题目的条件非常严格：
-
每个重复元素都只出现 两次
-
只有一个元素出现 一次
于是：
-
每一对相同元素都会变成
0 -
最终只剩下那个落单的数
如果题目条件变了，比如：
-
其他元素出现 三次
-
或者有 两个 元素只出现一次
那么这个最基础的异或写法就不能直接用了。
这也是为什么刷题时一定要注意题目条件，因为很多“技巧题”的成立都依赖于条件本身。
完整总结
这道题属于那种：
-
入门时可以用哈希表轻松做出来
-
进一步优化时可以学到位运算思想
非常适合作为“从普通解法过渡到技巧解法”的经典题。
我们可以这样理解这两种方案：
哈希表方案
优点是直观，容易想到。
核心就是：
-
先统计
-
再查找
异或方案
优点是简洁高效。
核心就是利用异或的三个性质：
-
a ^ a = 0 -
a ^ 0 = a -
异或满足交换律和结合律
因此，数组中所有成对元素都会被消掉，最后剩下的就是答案。
最后一句
如果这题你已经能写出哈希表版本，那说明你已经把题做出来了。
而如果你进一步理解了异或版本，那你掌握的就不只是这道题本身，而是一种在很多位运算题里都非常重要的思维方式。
