LeetCode 260. 只出现一次的数字 III

2026-05-27 HGNULB 约 4 分钟

文章信息 12 个分类 3 个标签

分类

LeetCode CodeTop 中等未解决 20-50 字节跳动美团快手腾讯滴滴华为虾皮

题目描述

✅ 260. 只出现一次的数字 III

题意分析

数组里恰好有两个数字只出现一次，剩下的每个数字都不多不少出现两次，要求把这两个「落单」的数字都找出来，返回顺序不作要求。

约束给得非常直白：要求时间线性、额外空间常数。这两条同时出现，等于把哈希表、排序、集合这些常规手段全部否掉了——哈希表能做到线性但空间是 $O(n)$，排序空间够省但时间是 $O(n\log n)$。能同时满足两条的工具很少，题目实际上是在指定方向。另外「其余数字恰好出现两次」这个条件非常强，它保证了重复元素总能两两配对，这是后续一切推导的基础。

边界方面：数组长度至少为 2，最小情形就是只有两个互不相同的数字；元素可以是负数，因此参与运算时要按补码理解每一位；两个答案本身可能一正一负，也可能同号。答案是集合语义，返回 [a, b] 和 [b, a] 都算对。

解法：异或分组

核心思路

若只有一个数字出现一次，把所有元素异或即可，因为 x ^ x = 0。本题有两个目标数，设为 a、b，第一次遍历后得到 xor = a ^ b；其余成对数字都已抵消。

因为 a != b，所以 xor != 0，它至少有一个二进制位为 1。取 lowbit = xor & -xor 得到最低位的 1；这一位上 a、b 必然一个为 0、一个为 1。按这一位分组时，两个目标数会被分开，而两个相同的数字一定进入同一组并继续抵消。

第二次遍历只异或该位为 0 的一组，结果就是其中一个目标数 first；另一个可由 xor ^ first 得到。正确性来自两个不变量：相同数字不会被拆组，两个目标数一定被拆组，因此选中组里除一个目标数外，其余元素都能两两抵消。

解题步骤

第一次遍历数组，异或所有元素，得到两个目标数的异或值 xor。

计算 lowbit = xor & -xor，选出两个目标数不同的最低二进制位。

第二次遍历，把满足 (num & lowbit) == 0 的元素异或到 first；该组内的重复数字会全部抵消。

计算 second = xor ^ first，返回两个结果，顺序不限。

例如 [1,2,1,3,2,5] 全部异或后为 6，二进制是 110，lowbit = 2。按这一位分组后，一组为 [1,1,5]，异或得到 5；另一个数为 6 ^ 5 = 3。

代码实现

class Solution {
    public int[] singleNumber(int[] nums) {
        int xor = 0;
        for (int num : nums) {
            xor ^= num;
        }

        int lowbit = xor & -xor;
        int first = 0;
        for (int num : nums) {
            if ((num & lowbit) == 0) {
                first ^= num;
            }
        }
        return new int[]{first, xor ^ first};
    }
}

func singleNumber(nums []int) []int {
    xor := 0
    for _, num := range nums {
        xor ^= num
    }

    lowbit := xor & -xor
    first := 0
    for _, num := range nums {
        if num&lowbit == 0 {
            first ^= num
        }
    }
    return []int{first, xor ^ first}
}

复杂度分析

时间复杂度：$O(n)$，两次线性遍历只做常数次位运算。

空间复杂度：$O(1)$，分组只体现在条件判断中，没有创建额外容器。

关键点总结

异或能在常数空间内消除所有出现偶数次的数字。

xor 的任意一个 1 位都能区分两个目标数；xor & -xor 只是最方便的取法。

分组成立的关键是：相同数字在选定位上的值相同，绝不会被拆开。

面试时应重点讲清“为什么能分开两个目标数、为什么重复数仍能抵消”，而不只是背 lowbit 公式。

易错点总结

直接用整个 xor 分组不可靠。对 [1,2,1,3,2,5]，3 & 6 和 5 & 6 都非零，两个目标数仍会落入同一组。

xor & (xor - 1) 是清除最低位的 1，不是提取最低位的 1；正确写法是 xor & -xor。

分组条件应与 0 比较，不能写成 (num & lowbit) == 1；当 lowbit = 2 时，结果只会是 0 或 2。

不能在第一次遍历中同步分组，因为 lowbit 依赖最终的 xor，必须先完整扫描一次。

Java 和 Go 的有符号整数按补码位运算，xor 为最小负数时 lowbit 仍可正确保留符号位，不需要特殊分支。

相似题目

题目	难度	考察点
136. 只出现一次的数字	简单	只有一个落单数，全员异或即为答案，本题的基础形态
137. 只出现一次的数字 II	中等	其余数字出现三次，异或失效，改用按位计数模 3
LCR 004. 只出现一次的数字 II	中等	137 同题，适合练习状态机写法的两变量位运算实现
剑指 Offer 56 - I. 数组中数字出现的次数	简单	与本题完全同解，可作为异或分组手法的重复演练
剑指 Offer 56 - II. 数组中数字出现的次数 II	中等	出现三次的变体，考察从异或抵消切换到逐位统计的思路