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

这道题到底在问什么

输入

nums = [1,2,1,3,2,5]

输出

[3,5]（1、2 各出现两次，只有 3 和 5 落单）

最优解：一步一步想明白

1. 3两把钥匙：xorAll = 全体异或 = a^b；diff = xorAll 最低位的 1，用它把 a 和 b 分到两组里各自捞出来。下面一帧帧演。
2. 4第一趟开始。准备一个累加器 xorAll = 0，从左到右把每个数异或进去。
3. 5指针走到下标 0，这一格是 1。把它异或进 xorAll（当前 xorAll = 0）。
4. 6异或完成：xorAll 从 0 变成 1。下标 0 及之前的数都已处理（标蓝）。
5. 7指针走到下标 1，这一格是 2。把它异或进 xorAll（当前 xorAll = 1）。
6. 8异或完成：xorAll 从 1 变成 3。下标 1 及之前的数都已处理（标蓝）。
7. 9指针走到下标 2，这一格是 1。把它异或进 xorAll（当前 xorAll = 3）。
8. 10异或完成：xorAll 从 3 变成 2。下标 2 及之前的数都已处理（标蓝）。
9. 11指针走到下标 3，这一格是 3。把它异或进 xorAll（当前 xorAll = 2）。
10. 12异或完成：xorAll 从 2 变成 1。下标 3 及之前的数都已处理（标蓝）。
11. 13指针走到下标 4，这一格是 2。把它异或进 xorAll（当前 xorAll = 1）。
12. 14异或完成：xorAll 从 1 变成 3。下标 4 及之前的数都已处理（标蓝）。
13. 15指针走到下标 5，这一格是 5。把它异或进 xorAll（当前 xorAll = 3）。
14. 16异或完成：xorAll 从 3 变成 6。下标 5 及之前的数都已处理（标蓝）。
15. 17第一趟结束。所有成对的数互相抵消，xorAll = 6，它正好等于两个落单数 a 与 b 的异或值。
16. 18取 xorAll 最低位的那个 1：diff = xorAll &(-xorAll) = 2。a 和 b 在这一位上一定不同，用它把它们分到两组。
17. 19第二趟开始。两个累加器 a=0、b=0。按「这个数和 diff 与一下是不是 0」把每个数分进 A 组或 B 组。
18. 20指针到下标 0，值 1。1 和 diff(2) 与一下得 0，为 0，分到 B 组。
19. 21B 组（红）：b 从 0 异或 1 变成 1。每组里成对的数还是会抵消。
20. 22指针到下标 1，值 2。2 和 diff(2) 与一下得 2，不为 0，分到 A 组。
21. 23A 组（绿）：a 从 0 异或 2 变成 2。每组里成对的数还是会抵消。
22. 24指针到下标 2，值 1。1 和 diff(2) 与一下得 0，为 0，分到 B 组。
23. 25B 组（红）：b 从 1 异或 1 变成 0。每组里成对的数还是会抵消。
24. 26指针到下标 3，值 3。3 和 diff(2) 与一下得 2，不为 0，分到 A 组。
25. 27A 组（绿）：a 从 2 异或 3 变成 1。每组里成对的数还是会抵消。
26. 28指针到下标 4，值 2。2 和 diff(2) 与一下得 2，不为 0，分到 A 组。
27. 29A 组（绿）：a 从 1 异或 2 变成 3。每组里成对的数还是会抵消。
28. 30指针到下标 5，值 5。5 和 diff(2) 与一下得 0，为 0，分到 B 组。
29. 31B 组（红）：b 从 0 异或 5 变成 5。每组里成对的数还是会抵消。
30. 32两趟扫完。A 组异或剩下 a=3，B 组异或剩下 b=5，这两个就是只出现一次的数：[3, 5]。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

def singleNumber(nums):
    xor_all = 0
    for x in nums:            # 第一趟：全体异或
        xor_all ^= x          # 成对抵消，剩 a^b
    diff = xor_all & (-xor_all)   # 取最低的 1 位
    a = b = 0
    for x in nums:            # 第二趟：按 diff 位分组
        if x & diff:
            a ^= x            # A 组
        else:
            b ^= x            # B 组
    return [a, b]

vector<int> singleNumber(vector<int>& nums){
    long xorAll = 0;
    for (int x : nums) xorAll ^= x;
    int diff = xorAll & (-xorAll);
    int a = 0, b = 0;
    for (int x : nums) {
        if (x & diff) a ^= x;
        else          b ^= x;
    }
    return {a, b};
}

public int[] singleNumber(int[] nums) {
    int xorAll = 0;
    for (int x : nums) xorAll ^= x;
    int diff = xorAll & (-xorAll);
    int a = 0, b = 0;
    for (int x : nums) {
        if ((x & diff) != 0) a ^= x;
        else                 b ^= x;
    }
    return new int[]{a, b};
}

复杂度

面试官可能追问