题目：
给你一个非空整数数组nums，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。
题解：
我觉着这是很有意思的一道题
该问题看似简单，但在时间和空间复杂度限制下，非常考察对位运算的理解。
一、最直观的思路（为什么不选）
1，使用哈希表统计次数
最容易想到的方式是：
使用哈希表记录每个数字出现的次数
再遍历哈希表，找出次数为 1 的元素
问题：
需要额外的存储空间
空间复杂度为
O(n)
而本题的隐含要求是：
使用常量额外空间
2， 排序后相邻比较
另一种思路是：
对数组排序
成对比较相邻元素
问题：
排序时间复杂度至少为
O(n log n)不满足最优解要求
二、最优解的核心思想：异或运算
1，什么是异或（XOR）
异或运算有几个非常重要的性质：
相同的数异或为 0
a ^ a = 0任何数与 0 异或仍是它本身
a ^ 0 = a异或满足交换律和结合律
a ^ b ^ a = b
2，这些性质意味着什么？
在数组中：
每个出现两次的数字：
x ^ x = 0所有成对的数字最终都会“抵消”为 0
剩下的唯一一个数：
0 ^ single = single
只出现一次的数字一定会被保留下来
三、算法思路（核心逻辑）
初始化一个变量
res = 0遍历数组中每一个元素
将当前元素与
res进行异或运算遍历结束后，
res就是只出现一次的数字
整个过程：
不需要额外的数据结构
只做一次遍历
完全利用位运算完成
四、总结
本题的关键不在于遍历，而在于如何“消掉”重复元素
异或运算天然适合处理：
成对出现
只剩一个不同值
这是位运算在算法题中的经典应用
一句话总结：
利用异或“相同为零、不同保留”的特性，让所有成对数字互相抵消，最终剩下的就是答案。
class Solution { public: int singleNumber(vector<int>& nums) { int ans = 0; for (int x : nums) { ans ^= x; } return ans; } };
