只出现一次的数字 III：有两个只出现一次怎么找？（LeetCode 260）

简化版

数组里有两个元素只出现一次（设为 a、b），其余都出现两次，找出这两个。做法分两步：① 把所有数异或，成对的抵消，得到 a ^ b；② 取出 a^b 中任意一个为 1 的位（用 lowbit = (a^b) & -(a^b) 取最低位的 1），这一位上 a、b 必然不同，用它把所有数字分成两组（该位为 1 的一组、为 0 的一组），a、b 被分到不同组，成对的数会分到同一组。每组内各自异或，就分别得到 a 和 b。

详细版

int[] singleNumber(int[] nums) {
    int xorAll = 0;
    for (int n : nums) xorAll ^= n;        // ① 得到 a ^ b

    int diff = xorAll & (-xorAll);         // ② 取 a^b 最低位的 1（a、b 在此位不同）

    int a = 0, b = 0;
    for (int n : nums) {
        if ((n & diff) != 0) a ^= n;       // 该位为 1 的一组
        else                 b ^= n;       // 该位为 0 的一组
    }
    return new int[]{a, b};
}

第一步：全异或消掉出现两次的，剩 a ^ b（a≠b 所以非 0）。
第二步：a^b 某位为 1 ⇒ a、b 在该位相异。用这一位分两组，把「找两个」拆成两个「找一个」。
x & (-x)：取最低位的 1（lowbit），是选分组位的便捷方式。
复杂度：O(n) 时间、O(1) 空间。

完整版教学

一、难点：有两个答案，异或全消不干净

136 题只有一个单独的数，全异或直接得答案。这里有两个单独的数 a 和 b，全异或后成对的消掉，剩下的是 a ^ b——两个答案的异或值，还没分开。核心难点就是：如何从 a ^ b 把 a 和 b 拆出来。

二、第一步：全异或得到 a ^ b

遍历数组全部异或。出现两次的数两两抵消（x^x=0），最后 xorAll = a ^ b。因为 a ≠ b（题目保证两个不同的数），所以 a ^ b ≠ 0——至少有一个二进制位是 1。这个「非 0」是下一步的钥匙。

三、第二步：找一个「a、b 相异」的位来分组

a ^ b 中某位为 1，意味着a 和 b 在这一位上恰好不同（一个 0、一个 1）——这正是异或「不同为 1」的含义。我们随便挑一个为 1 的位（最方便的是最低位的 1），拿它当「分组开关」：

该位为 1 的所有数字 分为一组；
该位为 0 的所有数字 分为另一组。

关键性质：

a 和 b 一定被分到不同组（因为它们在这一位不同）。
出现两次的数，两个副本这一位相同，必然分到同一组（同一个数，同一位当然一样）。

于是每组内部：一个单独的数 + 若干成对的数。组内全异或，成对的消掉，剩下那个单独的——一组得 a，另一组得 b。「找两个」就被拆成两个独立的「找一个」。

四、为什么用 lowbit `x & (-x)` 取分组位

要选「a^b 中一个为 1 的位」，最简便的是取最低位的 1：diff = xorAll & (-xorAll)。

原理：补码下 -x = ~x + 1，x & (-x) 恰好只保留 x 最低位的 1、其余清零。得到的 diff 是一个「只有那一位是 1」的掩码。判断某数 n 属于哪组，用 (n & diff) != 0——非 0 说明 n 在那一位是 1，归第一组，否则第二组。用最低位纯粹是方便，用任意一个为 1 的位都行。

五、完整走一遍

nums = [1,2,1,3,2,5]，单独的是 3 和 5。

全异或：1^2^1^3^2^5 = 3^5 = 011 ^ 101 = 110（即 6）。xorAll = 6。
diff = 6 & (-6) = 010（最低位的 1，即第 1 位）。3=011 该位是 1，5=101 该位是 0 → 分到不同组。✔
分组异或：该位为 1 的组 {1,3,1,3?}… 实际按 (n&2)!=0 分：{2,3,2}→2^3^2=3；另一组 {1,1,5}→1^1^5=5。得 a=3, b=5。✔

六、分组位保证两个答案被分开

全异或得到 xor=a^b，因为 a!=b，它至少有一位为 1。选择任意一个这样的位作为掩码，都能保证 a、b 在该位取值不同；相同的成对数字必进入同一组并在组内抵消。lowbit 只是稳定取出一个差异位的便捷方式。

数组 [1,2,1,3,2,5]
全异或 xor = 3 ^ 5 = 6 = 110₂
mask = xor & -xor = 010₂
第 1 位为 0 的组：1,1,5 -> 异或得 5
第 1 位为 1 的组：2,2,3 -> 异或得 3
答案 [5,3]，顺序可任意

校验维度	本题必须保持的结论
循环/递推不变量	分组后每对重复元素始终同组，两个单独元素必在不同组；各组都退化成 Single Number I。
边界条件	`xor` 不会为 0，因为题设保证两个单独元素不同；答案顺序通常不作要求。
复杂度与代价	两次线性扫描 O(n)，两个累计值和一个掩码 O(1)。
自检方式	用最小输入、典型输入和触及边界的输入分别手推，结果应与定义一致。

这组推演的作用不是替代证明，而是把抽象规则落到每一步状态变化上。面试写完代码后，应主动指出不变量如何保证不漏解，以及边界为何不会越界或死循环。若手推结果与定义不一致，应先修正状态语义，而不是继续给代码打补丁。

七、面试现场如何验证这道题

位运算题的代码通常很短，真正容易错的是把数学整数、固定宽度位模式和语言移位规则混在一起。本题应先复述这条不变量：分组后每对重复元素始终同组，两个单独元素必在不同组；各组都退化成 Single Number I。只有代码的初始化、更新顺序和终止条件都维持它，样例通过才具有证明力。

典型路径从“数组 [1,2,1,3,2,5]”开始手推，最后应得到“答案 [5,3]，顺序可任意”。
边界复核：xor 不会为 0，因为题设保证两个单独元素不同；答案顺序通常不作要求。
代价复核：两次线性扫描 O(n)，两个累计值和一个掩码 O(1)。
用全 0、只有一个 1、最高位为 1 三类位模式检查掩码。
涉及负数时把值写成固定宽度补码，确认使用 >> 还是 >>>。
涉及左移时检查移位距离和溢出后是否仍符合题目的位模式语义。

最后要主动构造一个“少写一次循环、改变一个不等号或交换两行更新就会失败”的反例。能说清反例破坏了哪条不变量，比只报出复杂度更能证明真正掌握了算法。

记忆钩子：本题的代码可以压缩，但“分组后每对重复元素始终同组，两个单独元素必在不同组；各组都退化成 Single Number I。”这条正确性主线不能省。

八、常见误区与追问

误区：可以按奇偶性固定分组。 若两个答案同奇同偶就无法分开，必须选择 a^b 中确实为 1 的差异位。
误区：重复元素的一对可能被分到不同组。 两个值完全相同，在任何固定掩码位上的结果也完全相同。
误区：xor & -xor 得到的是最低位下标。 它得到的是只有该位为 1 的掩码值，不是数值下标。
追问：xor 为负数时 lowbit 还有效吗？ 有效，固定宽度补码下 x&-x 仍保留最低位 1。
追问：能否只扫描数组一次？ 必须先知道分组掩码才能分类，通常需要一次求 xor、一次分组，共两遍。
追问：若有三个只出现一次的数怎么办？ 单个差异位不再保证递归分组可唯一恢复，需要更强题设或其他计数结构。

九、加强记忆

只出现一次的数字 III（两个单独）= 「先异或、再按位分组」。第一步全异或得 a^b（成对消掉，因 a≠b 故非 0）；第二步取 a^b 一个为 1 的位（lowbit = x & -x 取最低位 1）当分组开关——a、b 在此位相异必分到不同组，成对的数必在同组；两组各自异或，分别得到 a、b。把「找两个」拆成两个「找一个」。O(n) O(1)。核心一句：异或求出两者之差，用差异位把它俩劈开。

简化版

详细版