最近在重新整理位运算相关的刷题笔记正好写到系列的第5篇。今天要聊的这道题LeetCode编号260名字叫“只出现一次的数字 III”——在中文互联网里它的前面还有一道136和一道137分别对应“成对出现里找一次”和“出现三次里找一次”。到了这一题画风开始不一样了一堆数字里有且仅有两个数字只出现了一次其余数字全部成对出现要你一次性把这两个“单数”都找出来。第一直觉是异或。毕竟136题的答案就是一行异或把所有数字全部 ^ 在一起成对的直接清零剩下的就是那个唯一的数。但260题不行——全部异或完得到的是两个单数的异或结果 x ^ y。你不是要找一个数你要找的是两个数一个异或结果不够用。这篇文章我就把这道题的完整解法、推导过程以及我在实际调试中踩过的坑都拆开讲清楚。适合刚刷完136题、准备进阶位运算的读者也适合面试前临时抱佛脚想快速掌握这套“分组异或”套路的朋友。1. 题目解读两个“单数”与一堆“双数”的迷宫1.1 原题描述与输入输出示例题目要求是这样的给你一个整数数组 nums其中恰好有两个元素只出现一次其余所有元素都恰好出现两次。找出只出现一次的那两个元素。你可以按任意顺序返回答案。举个例子输入nums [1, 2, 1, 3, 2, 5] 输出[3, 5] 输入nums [-1, 0, 1, 0, -1, 2] 输出[1, 2]注意负数也会出现数字大小没有限制Python里不用太担心溢出但后面我会提到一个和语言特性相关的坑。数据范围通常是数组长度 2 到 30000 左右每个数字在 32 位有符号整数范围内。进阶要求很有意思你的算法应该具有线性时间复杂度并且不使用额外空间。翻译一下就是——时间复杂度 O(n)空间复杂度 O(1)。这基本就是在明示你要用位运算别想着用哈希表。1.2 跟136题、137题放在一起看思路有什么不同把这三道题放一起比较能很清楚地看到位运算题的递进关系题目其他数字出现次数要找的数字个数核心位运算技巧只出现一次的数字 I1362次1个全员异或只出现一次的数字 II1373次1个逐位统计取模 / 有限状态机只出现一次的数字 III2602次2个全员异或 分组异或136题是“异或清零”的入门应用137题开始涉及到“模3”的概念260题则是把异或结果继续拆分核心从“异或等于0”升级成了“异或结果中的某个1位可以把两个目标数字分到不同组”。很多人在260题卡住不是因为看不懂异或而是因为思维还停留在“异或只能得到一个数”的层面。一旦你想明白“异或得到两个数的差异信息差异信息又能反过来做分组”这道题就彻底通了。1.3 常规解法的局限哈希表和排序为什么不够“高级”我见过不少同学第一反应是from collections import Counter return [k for k, v in Counter(nums).items() if v 1]这写法没错能过但面试官大概率会追问一句“能不能不用额外空间”哈希表空间复杂度是 O(n)显然不满足题目的进阶要求。排序也能做nums.sort() res [] i 0 while i len(nums): if i len(nums) - 1 or nums[i] ! nums[i 1]: res.append(nums[i]) i 1 else: i 2 return res但排序时间复杂度是 O(nlogn)也不满足线性复杂度要求。所以这道题的标准答案基本就是位运算分组这一条路。2. 异或基本功复习从136题到260题的思维跳跃2.1 异或的三条核心性质在讲260题之前必须把异或的三条性质刻在脑子里归零律a ^ a 0。一个数和自己异或结果为0。恒等律a ^ 0 a。一个数和0异或还是它自己。交换律和结合律a ^ b ^ c a ^ (b ^ c) (a ^ c) ^ b。运算顺序不影响结果。这三条性质组合在一起就是“全员异或找唯一数字”的全部原理。不管数组怎么乱序成对的数字最终都会两两抵消成0剩下的就是那个孤零零的目标。用生活里的例子理解异或就像“消消乐”两个相同的方块碰到一起就消失0就是什么都没有任何方块跟“什么都没有”放在一起还是那个方块本身。2.2 136题的经典解法回顾136题“只出现一次的数字”解法长这样def singleNumber(nums): res 0 for num in nums: res ^ num return res逐行解释就是初始化一个0然后遍历数组把每个数字都和res做异或。假设数组是 [2, 1, 2]运算过程是0 ^ 2 22 ^ 1 33 ^ 2 1。因为两个2互相抵消了最后只剩下1。这个解法简洁到让人觉得位运算“不过如此”但这种简洁恰恰是陷阱——它让你以为所有“找单数”的题都是一行异或搞定。到了260题你全员异或完得到的不是答案而是一个“加密后的差异值”。2.3 260题的关键卡点一个XOR结果不够还差一个分组信息现在假设数组是 [1, 2, 1, 3, 2, 5]。全员异或的过程是1 ^ 2 ^ 1 ^ 3 ^ 2 ^ 51和1抵消2和2抵消最后剩下 3 ^ 5结果是6二进制是 110。这个6告诉了我们什么它告诉了我们3和5的异或结果这个结果的每一个二进制位都表示3和5在那一位上是否不同。比如 3 的二进制是 0115 的二进制是 101异或得到 110说明第1位从0开始和第2位不同第0位相同。问题来了知道它们在哪几位不同怎么把这个信息变成“分离两个数”的工具这就是这道题最核心的思维跳跃——用差异位做分组依据。3. 核心解法分组异或把两个单数拆进两组3.1 第一步全员异或拿到差异值这一步和136题一模一样代码也不用改xor_all 0 for num in nums: xor_all ^ num唯一要注意的是xor_all一定不为0。为什么因为两个要找的数字不一样题目说了恰好两个元素只出现一次这两个元素必然不同它们异或的结果一定有某个二进制位是1。如果它们相等那它们就不是两个独立的目标数字了而是同一堆成对数中的一对。3.2 第二步用 lowbit 找到最右侧的“1”位xor_all 的二进制里可能有多个1随便挑一个就能用来分组。但工程上最方便的做法是取最右侧那个1也就是 lowbit。lowbit xor_all (-xor_all)这个式子有点反直觉尤其是-xor_all在Python里到底怎么参与位运算我后面用专门一节来解释。这里先记住结论它会返回一个只包含一位是1的数字这个1的位置正好是 xor_all 最低位的那个1。比如 xor_all 6二进制110lowbit 2二进制010。这个2就是6的最低位1的位置——第1位。3.3 第三步按照 lowbit 分组分别异或拿到 lowbit 之后遍历原数组把每个数字按照“这一位是否为1”分成两组num1, num2 0, 0 for num in nums: if num lowbit: num1 ^ num else: num2 ^ num return [num1, num2]关键在于成对的相同数字二进制完全一样所以它们必然被分到同一组异或后互相抵消。而3和5因为在这一位上不同一个被分到 num1 组另一个被分到 num2 组。每组剩下的就是分到该组的目标数字。3.4 完整代码与逐行注释把三部分拼起来就是完整题解def singleNumber(nums): # 第一步全员异或得到两个目标数字的异或结果 xor_all 0 for num in nums: xor_all ^ num # 第二步取异或结果中最低位的1作为分组依据 # 这个1对应的位恰好是num1和num2不同的最低位 lowbit xor_all (-xor_all) # 第三步按lowbit分组分别异或 num1, num2 0, 0 for num in nums: if num lowbit: num1 ^ num else: num2 ^ num # 题目说可以按任意顺序返回但为了输出稳定升序返回更友好 if num1 num2: num1, num2 num2, num1 return [num1, num2]这个解法的时间复杂度是 O(n)空间复杂度 O(1)。两个循环每个循环遍历一次数组常数级内存。4. 为什么分组可行正确性证明与直觉建立4.1 关键性质1相同的数字必然被分到同一组这一点特别容易理解但很多人在推导时会忽略。设想数组里有两个5它们的二进制完全相同比如101。lowbit 是010判断条件num lowbit对两个5来说结果完全一样要么都进入num1组要么都进入num2组。所以成对的数字不会拆散它们进入同一组后异或抵消对最终结果没有任何干扰。这个性质保证了我们的分组操作不会“误伤”普通元素。4.2 关键性质2两个目标数字必然被分到不同组为什么一定能分开因为 lowbit 是从 xor_all 中取出来的1位而 xor_all x ^ y。异或结果的某一位是1意味着x和y在这一位上的值不同——一个为0一个为1。既然不同那么用num lowbit去判断时x和y必然一个结果为真一个结果为假。所以x进 num1 组y就进 num2 组永远不会被分到同一组。一个有趣的现象是lowbit 选哪一位其实无所谓。只要是 x ^ y 中为1的位都能起到分离作用。取最低位的1只是写起来最方便。4.3 lowbit 的几何意义x (-x)到底干了什么很多初学者第一次看到x (-x)会懵因为在数学里一个数跟它的相反数按位与看起来没什么道理。但在计算机里负数是以补码形式存储的-x等于~x 1按位取反再加1。举个例子设 x 6二进制是 1106 ...00000110 -6 ...11111010 (取反加1)按位与...00000110 ...11111010 ...00000010得到2也就是 010正是110中最右侧那个1的位置。这个操作在图形学、树状数组BIT里也很常见所以记牢它后面很多地方都用得上。我用一个比喻帮你记x (-x)就像是“从一串数字里把最靠右的那个1单独拎出来其余全部清零”。4.4 复杂度分析与其他解法的对比解法时间复杂度空间复杂度优缺点哈希表O(n)O(n)简单直观但不满足进阶要求排序O(nlogn)O(logn)依赖排序不够优雅分组异或O(n)O(1)标准答案位运算精髓从对比能看出来分组异或在时间、空间上都占优而且代码量极短。这也是位运算题在面试中高频出现的根本原因——用很小的代码量考察你有没有建立起“用二进制表达状态”的思维。5. 延伸思考如果“其他数字出现三次”位运算怎么打5.1 题目变形从“成对”变成“三连”260题讲完很多人会好奇如果其他数字不是出现两次而是出现三次只有一个数字只出现一次那怎么办这其实是137题“只出现一次的数字 II”的考察点。这类题就不能简单用异或了因为相同的数出现三次异或三次后还是它本身——异或的“消消乐”只在偶数次出现时才生效。所以我们需要换一种策略既然一个bit位上1出现的次数如果是3的倍数说明这个bit在目标数字上是0如果不是3的倍数说明目标数字在这个bit上是1。5.2 解法一逐位统计做模3运算最容易理解的方法是统计每个bit位上1出现的总次数然后对3取模def singleNumber(nums): res 0 for i in range(32): cnt 0 for num in nums: cnt (num i) 1 if cnt % 3 ! 0: res | (1 i) # Python的整数没有固定位数需要手动处理负数 if res 2 ** 31: res - 2 ** 32 return res这个思路很直白把每个数字拆成32个bit统计每个bit上的1的个数。出现3次的数字每个bit贡献的1的次数要么是0要么是3的倍数取模后都是0。只有目标数字贡献的那个bit取模后可能留下1。这里有个Python特有的坑其他语言int通常是有符号32位最高位是符号位如果res的第31位从0开始是1说明是负数。但Python的int是无限精度的左移出来的高位不会自动变成符号所以需要手动判断并减掉2的32次方把它转成真正的负数。这种方法时间复杂度是 O(32n)虽然常数比较大但胜在通用。如果把题目再改成“其他数字出现k次”只需要把% 3和// 3的逻辑改成% k就行。5.3 解法二有限状态机用两个变量模拟三进制逐个bit统计虽然直观但常数时间稍大面试官可能会期待更精致的解法——用两个变量 ones 和 twos 实现的有限状态机。def singleNumber(nums): ones, twos 0, 0 for num in nums: ones (ones ^ num) ~twos twos (twos ^ num) ~ones return ones这个代码很短但理解起来有点门槛。核心思路是对于每一个bit位我们用两个二进制位ones和twos来记录该bit位出现的1次数的状态状态编码如下twosones含义00该位1出现0次01该位1出现1次10该位1出现2次11非法状态不出现处理一个新的数字时相当于在这个状态机上走一步。出现一次状态从00到01出现第二次状态从01到10出现第三次状态从10回到00。这样同样的数字在连续出现三次后所有bit位回到0而目标数字只贡献了一次状态变化最终留在01状态也就是 ones 的值。为什么先更新 ones 再更新 twos因为 twos 的更新依赖新的 ones这样才能避免出现非法状态11。这一步是很多文章没讲透的地方实际推导一下任一位上的真值表就能验证。5.4 方法对比与选择建议对137题来说逐位统计法更容易写对尤其是在面试高压环境下不容易出错。状态机法代码更炫酷但需要你有把握講清楚原理。我个人建议面试时先讲逐位统计再引出状态机优化如果时间紧张只讲逐位统计也完全能过关。顺带一提260题的分组异或其实和137题的状态机有一个共同点它们都在“用二进制位做事后的信息重组”。理解了这一点位运算系列的核心套路基本就全部拿下了。6. 刷题实录那些容易踩的坑和面试讲解技巧6.1 Python位运算的“无限整数”陷阱Python的整数不像C和Java那样有固定位数这给位运算带来了两个常见坑。第一个坑在137题里已经提到当最终答案的二进制最高位是1时需要手动转成负数。第二个坑是你以为~x只是“按位取反”但 Python 的~x等于-x - 1这导致在内存中它表现为无限位数的补码。不过在(ones ^ num) ~twos这样的表达式里高位全1的~twos反而不会干扰结果因为ones ^ num的高位都是0按位与之后高位仍然是0。所以你不必担心这个式子算错但心里要有数这不是巧合而是Python补码表示法的自然结果。6.2 lowbit 在 Python 中的表现在260题里lowbit xor_all (-xor_all)对正数、负数都成立。但有个边角情况要留意如果 xor_all 恰好是 -2147483648也就是 -2^31-xor_all是 2147483648超出了32位有符号整数范围。在 C 里这可能导致溢出但Python不会因为Python的整数可以无限扩展。这道题的数据范围一般不会大到触发这种极端值但搞清楚原因面试时如果被追问也不虚。6.3 设计测试用例别只测正数刷题时我习惯拿三类用例测普通正数[1, 2, 1, 3, 2, 5]应该输出[3, 5]包含负数[-1, 0, 1, 0, -1, 2]应该输出[1, 2]极端重复[7, 7, 7, 7, 3, 5]这种多个重复数字混合的情况验证分组是否正确负数的二进制表示比正数复杂容易暴露出代码里 lowbit判断的边界问题。多跑几组心里就有底了。6.4 面试讲解的推荐路径面试官如果让你现场做这道题我建议你按照这个顺序讲先快速说明暴力解法和哈希表为什么不够优引出位运算的动机。复习136题的异或技巧明确“全员异或能得到唯一数字”只是基础。抛出卡点两个数字怎么办异或结果只是它们的“差异值”。引入lowbit利用差异值中的任意一个1位做分组把两个目标数字分开。最后补充正确性成对数字不会跨组目标数字必然分组分别异或即可。这套讲解路径的好处是即使面试官提前知道答案也能看到你的思维过程是清晰的而不是背题。6.5 后续练习方向如果这道题你能独立写出来位运算的“异或消消乐”和“分组信息提取”基本就过关了。接下来可以继续练这两个方向137题“只出现一次的数字 II”巩固模3思路268题“丢失的数字”、231题“2的幂”练习异或和lowbit的灵活运用把这些题放一起练你会慢慢发现位运算并不是靠死记硬背公式而是靠理解“位上是0还是1”这样一个最简单的事实。我在实际刷题中还有一个感受这类位运算题目光看题解很容易“眼睛会了手不会”。最好的办法是把每题的解释代码手敲一遍再自己从头推导一遍特别是从 xor_all 到 lowbit 再到分组的中间过程每一步都要能讲清楚为什么。能做到这一步面试时遇到位运算题你基本不会慌。