只出现一次的数字 图解题解

这道题的隐藏约束是常量空间

数组里除了一个数只出现一次，其余每个数都恰好出现两次，要把落单的那个找出来。题目额外钉了两条硬要求：线性时间、常量空间。找出现次数本身不难，难的是这两条约束把最顺手的工具全排除了——排序要 O(n log n) 时间，哈希表计数要 O(n) 额外空间。这道题真正考的，是知不知道有一种运算能在不占空间的前提下「记住并抵消」成对的数。

为什么只出现一次的数字要用异或

先看直觉解卡在哪：用哈希表统计每个数出现几次，再挑出计数为 1 的，时间 O(n) 达标，但表本身要 O(n) 空间，不满足常量空间。我们需要的是一种「聚合」——扫过所有数后只留一个变量，且成对的数在聚合过程中自动消失。

异或（按位比较，两位不同得 1、相同得 0）正好有这两条性质：a ⊕ a = 0，相同的数碰面就归零；a ⊕ 0 = a，零是不改变结果的单位元。于是把全部数异或进一个累加器 ans，出现两次的数两两抵消成 0，一串 0 异或下来不留痕迹，最后 ans 里剩的就是那个没有搭档的数。整段代码只有一个循环、一行 ans ^= x。

成对的数隔得很远，为什么也能抵消

异或满足交换律和结合律，一长串异或的结果与运算顺序无关——可以在脑子里把相同的数重排到相邻位置再算，结果不变。所以两个 5 无论一个在开头一个在结尾，最终都等价于紧挨着异或、抵消成 0。拿题目示例 [4,1,2,1,2,5,5,3,3,6,6] 验证：1、2、5、3、6 各自成对消光，只剩 4，与答案一致。这也解释了为什么累加器从 0 起步最干净：0 是单位元，第一个数异或进来天然等于它自己，不需要任何特殊处理。

复杂度怎么算，这招的适用边界在哪

时间 O(n)：数组扫一遍，每个数做一次异或。空间 O(1)：只用一个变量 ans，与数组规模无关——这正是哈希表方案给不了的。

但要清楚这招的边界：异或抵消靠的是「恰好成对」。如果题目改成其余数都出现三次、只有一个出现一次（LeetCode 137），三个相同的数异或剩下它自己，抵消失效；那类题得按二进制位统计每一位上 1 出现的总次数，对 3 取模来还原答案。面试里被追问变体时，能点出「异或只消偶数次出现」这条本质，比背出代码更值钱。

Python

def singleNumber(nums):
    ans = 0                # 累加器，从 0 开始
    for x in nums:
        ans ^= x           # 把每个数异或进来
    return ans             # 成对的都抵消，剩下落单的

C++

int singleNumber(vector<int>& nums){
    int ans = 0;
    for (int x : nums) ans ^= x;
    return ans;
}

Java

public int singleNumber(int[] nums) {
    int ans = 0;
    for (int x : nums) ans ^= x;
    return ans;
}