深入解析LeetCode 136：巧用异或运算，高效找出数组中唯一的“单身数字”
在算法面试和日常编程中，处理数组和查找特定元素是高频出现的场景。LeetCode第136题“只出现一次的数字”就是一个经典的入门级问题，它不仅考察对基础数据结构的理解，更巧妙地引入了位运算这一高效工具。本文将深入剖析这道题，从最直观的思路出发，逐步推导出最优解，并横向对比多种编程语言（如Java、JavaScript、Python、Go、C++）的实现，帮助你掌握问题本质，提升算法思维。
一、问题定义与核心挑战
题目要求非常简单：给定一个非空整数数组，其中某个元素只出现一次，其余每个元素均出现两次。你的任务是找出那个只出现一次的元素。题目附加了一个关键约束：你的算法应该具有线性时间复杂度（O(n)），并且只使用常量额外空间（O(1)）。
这意味着我们不能简单地使用嵌套循环（O(n²)）来暴力求解，也不能无节制地使用与数据规模成正比的额外内存（例如复制整个数组）。这个约束将我们引向更巧妙的解法。常见的直观思路，如使用哈希表统计次数或集合去重，虽然能解决问题，但往往无法同时满足时间和空间复杂度的双重要求。这正是本题的巧妙之处，它引导我们寻找一种“原地”且高效的算法。
二、位运算的魔法：异或（XOR）解法
要满足O(n)时间和O(1)空间，位运算中的异或（XOR）操作成为了破题的关键。异或运算有以下几个至关重要的性质，正是这些性质让它完美适配本题：
- 归零律：任何数与自身异或结果为0。即 a ⊕ a = 0。
- 恒等律：任何数与0异或结果为其本身。即 a ⊕ 0 = a。
- 交换律和结合律：异或运算满足交换律和结合律，即 a ⊕ b = b ⊕ a， (a ⊕ b) ⊕ c = a ⊕ (b ⊕ c)。
- 自反性：如果 a ⊕ b = c，那么 a ⊕ c = b， b ⊕ c = a。
基于这些性质，我们可以推导出本题的算法核心：将数组中所有的数字进行异或运算，出现两次的数字会相互抵消为0，最终的结果就是那个只出现一次的数字。
例如，对于数组 [4, 1, 2, 1, 2]，计算过程如下：
4 ⊕ 1 ⊕ 2 ⊕ 1 ⊕ 2 = 4 ⊕ (1 ⊕ 1) ⊕ (2 ⊕ 2) = 4 ⊕ 0 ⊕ 0 = 4
算法的实现极其简洁。我们初始化一个变量 res=0
class Solution {
public:
int singleNumber(vector<int>& nums) {int res=0;for (auto v:nums){res^=v;}return res;}};这种解法在Java、C++、Go等语言中几乎一致，在JavaScript/TypeScript中同样清晰。它是时间复杂度和空间复杂度的双优解，也是面试官最期望看到的答案。
[AFFILIATE_SLOT_1]三、其他可行解法的分析与对比
虽然异或解法是最优的，但理解其他解法有助于我们全面掌握数据结构。下面我们分析几种常见解法及其适用场景。
1. 集合增删法（HashSet）
这是最符合直觉的解法。我们遍历数组，如果当前数字不在集合中，就加入集合；如果已经在集合中，则将其移除。遍历结束后，集合中剩下的唯一元素就是答案。
优点：思路直观，易于理解和实现。
缺点：使用了O(n)的额外空间（最坏情况下集合需要存储约n/2个元素），不满足题目的常量空间要求。
class Solution {
public:
int singleNumber(vector<int>& nums) {// acm的话记得包含<unordered_set>头文件unordered_set<int> s; // 定义无序集合,查询/增删效率为O(1)for (int num : nums) {if (s.count(num)) { // 集合中已有该数字（出现第二次）s.erase(num); // 从集合删除} else { // 集合中无该数字（出现第一次）s.insert(num); // 加入集合}}// 最终集合中只有一个元素，返回该元素（*s.begin()取第一个元素）return *s.begin();}};2. 哈希表统计法（HashMap）
使用哈希表（或字典）记录每个数字出现的次数。第一次遍历数组进行计数，第二次遍历哈希表找出计数为1的键。
优点：通用性强，可轻松扩展到“找出出现k次的数字”这类问题。
缺点：需要两次遍历，且空间复杂度为O(n)。
#include <vector>#include <unordered_map> // 哈希表头文件using namespace std;class Solution {public:int singleNumber(vector<int>& nums) {unordered_map<int, int> count_map; // key=数字，value=出现次数// 统计每个数字的出现次数for (int num : nums) {count_map[num]++; // 不存在的key会自动初始化为0，再+1/*也可以写成下面这样，更好理解一点：看一下num在不在这个哈希表中，如果不在哈希表中，则查找到的是哈希表的尾后迭代器，那就需要新增。if (count_map.find(num) != count_map.end()) {count_map[num] += 1;} else {count_map[num] = 1;}*/}// 遍历哈希表找次数=1的数字for (auto& pair : count_map) {if (pair.second == 1) { // pair.second 是次数return pair.first; // pair.first 是数字}}return -1; // 题目保证有解，仅防止编译报错}};3. 数学技巧：集合求和差值法
利用数学公式：2 * (集合中所有唯一元素的和) - (数组中所有元素的和) = 只出现一次的数字。
原理：集合`set(nums)`包含了所有不重复的元素。假设唯一数是`x`，其他数都出现两次，那么：
2 * sum(set) = (x + 2*其他数之和)
sum(nums) = (x + 2*其他数之和)
两者相减：2*sum(set) - sum(nums) = x
优点：思路巧妙，代码简短。
缺点：可能存在整数溢出风险（对于大数），且创建集合同样需要O(n)空间。
#include <vector>#include <unordered_set>#include <numeric> // 求和函数 accumulate 的头文件using namespace std;class Solution {public:int singleNumber(vector<int>& nums) {unordered_set<int> s(nums.begin(), nums.end()); // 集合存储所有唯一元素// 手动遍历求和long long sum_set = 0;for (int num : s) {sum_set += num;}// 也可以用STL的accumulate函数，但acm要记得包含<numeric>头文件// long long sum_set = accumulate(s.begin(), s.end(), 0LL);//0LL表示以 long long 类型初始化累加值，否则 accumulate 会默认用 int 累加，可能溢出// 计算数组所有元素的和long long sum_nums = accumulate(nums.begin(), nums.end(), 0LL);return 2 * sum_set - sum_nums;}};四、多语言实现与要点总结
掌握算法的核心思想后，在不同语言中实现是水到渠成的事情。关键在于理解异或运算符在各语言中的表示（通常是 ^）。
- Java/C++/Go/JavaScript：直接使用
^运算符，循环结构实现。 - Python：可以使用
reduce函数配合operator.xor进行函数式编程，一行代码解决：from functools import reduce; from operator import xor; return reduce(xor, nums)。 - TypeScript：与JavaScript实现完全相同，只需注意类型标注。
⚠️ 注意事项：异或解法之所以有效，完全依赖于“其他数字出现偶数次（本题是两次）”这一前提。如果题目变为“只有一个数字出现一次，其余出现三次”，则异或法不再适用，需要考虑更复杂的位计数或数学方法。
[AFFILIATE_SLOT_2]五、举一反三与思维延伸
解决“只出现一次的数字”只是开始，LeetCode上还有一系列变体问题，可以进一步巩固位运算技巧：
- LeetCode 137. 只出现一次的数字 II：其他数字出现三次，唯一数字出现一次。需要设计一个状态机或按位统计。
- LeetCode 260. 只出现一次的数字 III：有两个数字只出现一次，其余出现两次。这需要先异或得到两个唯一数的异或值，再根据其中某一位为1的特征将数组分成两组，分别异或求解。
- 在现实中的应用：异或运算在加密、校验（如奇偶校验）、以及一些需要快速比较或切换状态的场景中非常有用。理解其性质对底层开发和性能优化至关重要。
给初学者的建议：遇到算法题时，先尝试最直观的解法，再分析其时间/空间复杂度，并思考在给定约束下是否有优化空间。从“能用”到“高效”的思考过程，正是算法能力提升的关键。
LeetCode 136题是一个绝佳的范例，它展示了如何利用数据本身的特性（出现次数为偶数）和运算的数学性质（异或），将一个看似需要额外空间的问题，优雅地转化为原地解决的方案。掌握这种“异或消消乐”的思想，不仅有助于你通过面试，更能深刻理解计算机底层运算的巧妙与力量。希望本文的详细拆解能帮助你融会贯通，在面对更复杂的位运算问题时也能游刃有余。