给你一个数组除一个数只出现一次外其余每个数都出现两次把它找出来。要求线性时间、常数空间。不准用哈希表空间不满足、不准排序后扫描时间不满足、更不准2×sum(set) − sum(nums)溢出且空间超标。正解只有一行returnfunctools.reduce(lambdaa,b:a^b,nums)第一次见这行代码的人几乎都会愣一下——为什么“成对出现的数”会在异或里自己消失因为它精确对应了异或最本质的三条性质。这三条性质撑起了整个位运算世界的半壁江山而很多人只记住了“异或是二进制的无进位加法”却没意识到它同时是一个完备的代数结构。今天把这三条讲透你会顺带理解二进制Trie为什么能用异或做贪心、lowbit到底在取什么。 题目速览30秒读懂题目1只出现一次的数字LC.136非空数组除某个元素只出现一次外其余均出现两次。找出那个只出现一次的元素。示例[2,2,1]→1[4,1,2,1,2]→4要求线性时间 常数空间。题目2只出现一次的数字IIILC.260延伸恰好有两个元素只出现一次其余均出现两次。找出这两个元素。示例[1,2,1,3,2,5]→[3,5]示例[-1,0]→[-1,0] 核心思路异或的三条性质异或XOR记作^是“两位不同则为1相同则为0”。真正让它在算法里大放异彩的是它的代数性质性质公式含义自反性a ^ a 0一个数和自己异或全部抵消恒等性a ^ 0 a和0异或原样保留交换律与结合律a ^ b b ^ a(a ^ b) ^ c a ^ (b ^ c)顺序无关可以先任意重排第三条是最容易被低估的。它意味着“一堆数异或起来”这个操作与输入顺序无关只与“每个数出现了几次”有关。于是nums [4, 1, 2, 1, 2] 全体异或 4 ^ 1 ^ 2 ^ 1 ^ 2 4 ^ (1 ^ 1) ^ (2 ^ 2) ← 交换结合律把成对的重排到一起 4 ^ 0 ^ 0 ← 自反性 4 ← 恒等性一句话核心异或只关心“出现次数的奇偶”——出现偶数次的全部归零出现奇数次的留下。这就是为什么它是天然的“奇偶计数器”而且成本只有O(1)空间。⚠️一个常见误解a ^ a 0只对偶数次成立。若其余元素出现三次LC.137异或就失效了——那时必须换成“逐位统计mod3”或“有限状态机”。记住这条边界比记住解法更重要。LC.260异或 分组现在有两个“单身”数字x、y。全体异或得到的是s x ^ y——两个数被混在了一起怎么拆开关键观察因为x ≠ y所以s ≠ 0s的二进制里至少有一位是1。而s的第k位为1意味着x和y在第k位上不同。于是我们拿到一个天然的分类标准按第k位是否为1把整个数组分成两组。x和y必然分在不同的两组成对出现的数字两个副本第k位相同必然落在同一组于是每组内部都退化成了LC.136——各自异或即得答案。取哪一位取s中最低的那个1最方便lowbit s (-s)这行代码在树状数组时已经出现过。这里给它一个更普适的解读n (-n)取出n的二进制中最低位的那个1所对应的权重它是位运算工具箱里的标准件之一。️ 图解算法手把手走一遍以nums [1, 2, 1, 3, 2, 5]为例答案[3, 5]。第一步全体异或逐元素累计步骤读入累计异或值二进制0—0000110 ^ 1 1001221 ^ 2 3011313 ^ 1 2010432 ^ 3 1001521 ^ 2 3011653 ^ 5 6110最终s 6 110₂正是3 ^ 5 6✓。注意中间值忽大忽小——异或不是累加是逐个抵消。第二步取lowbit分组s 6 110₂ lowbit s (-s) 110 010 010₂ 2lowbit 2说明我们按第1位是否为1来分组元素二进制第1位分组10010B组20101A组10010B组30111A组20101A组51010B组第三步两组各自异或A组第1位为12 ^ 3 ^ 2 3 ← 两个2抵消留下3 B组第1位为01 ^ 1 ^ 5 5 ← 两个1抵消留下5答案[3, 5]✓为什么分组后“成对的数不会散开”因为两个副本是同一个数第k位必然相同所以必然同组。这是整个算法成立的关键也是面试时最该讲清楚的一句。 代码实现Python JavaPython版classSolution:# ---------- LC.136 只出现一次的数字 ----------defsingleNumber(self,nums:list[int])-int:ans0forxinnums:ans^x# 成对的自我抵消单身的留下returnans# ---------- LC.260 只出现一次的数字III ----------defsingleNumberIII(self,nums:list[int])-list[int]:s0forxinnums:s^x# s x ^ y且s ! 0masks(-s)# lowbit取最低位的1作为分组依据ab0forxinnums:ifxmask:# 该位为1的一组a^xelse:# 该位为0的一组b^xreturn[a,b]Java版classSolution{publicintsingleNumber(int[]nums){intans0;for(intx:nums)ans^x;returnans;}publicint[]singleNumberIII(int[]nums){ints0;for(intx:nums)s^x;// s x ^ yintmasks(-s);// lowbitinta0,b0;for(intx:nums){if((xmask)!0)a^x;elseb^x;}returnnewint[]{a,b};}}⚠️防坑提醒必看s (-s)只在s ≠ 0时有意义。题目保证恰有两个单身数字所以s ≠ 0成立。分组判定用x mask位与结果非零不是x mask mask。Python整数是无限位补码语义-5 5一样得到lowbit无需额外处理。⏱️ 复杂度分析面试必问题目时间空间说明LC.136O(n)O(1)一遍扫描LC.260O(n)O(1)扫两遍先求s再分组解法时间空间评价哈希表计数O(n)O(n)❌ 违反常数空间排序后扫描O(nlogn)O(1)❌ 违反线性时间2×sum(set) − sumO(n)O(n)❌ 空间超标大数溢出全体异或O(n)O(1)✅ 唯一正解空间是这个系列里最“干净”的O(1)——只有一个整数变量在滚动。这也是为什么面试官爱考它它逼你放弃“记下来”的直觉改用“抵消掉”的直觉。 举一反三5道高频变体题题号题目与本题的关系LC.137只出现一次的数字II其余元素出现三次异或失效需逐位统计mod 3或有限状态机LC.645错误的集合异或 分组的变体LC.461汉明距离popcount(a ^ b)LC.421数组中两个数的最大异或值二进制Trie 贪心LC.268丢失的数字异或与“下标配对”的经典技巧 面试追问模拟提前准备惊艳全场Q1为什么a ^ a 0从定义出发异或是“两位不同为1”。a与自己做异或第k位上两个比特必然相同所以结果每一位都是0。这是逐位成立的与进位无关——这正是异或比加法好用的根本原因没有进位位与位之间彻底解耦。Q2不用临时变量交换两个数a ^ b; b ^ a; a ^ b可靠吗原理成立但工程上不推荐① 若a和b是同一个变量同一地址三步之后会清零② 可读性差编译器本就会做寄存器优化③ 对浮点数、对象完全不适用。面试里说“我知道原理但不会这么写”是加分项。Q3LC.260的分组位换成任意为1的位行不行行。只要取s中任意一个为1 的位即可完成分组lowbit只是最容易写的一种。若要取最高位的1可以用1 (s.bit_length() - 1)效果完全相同。Q4出现三次的情况怎么做LC.137异或只能区分奇偶三次需要mod3。两种做法①逐位统计——对每一位统计1的个数对3取模O(32n)②有限状态机——用两个变量ones/twos表示“出现1次的位”和“出现2次的位”一遍扫描O(n)、O(1)空间是最优解。 实战小技巧刷题党必备口诀自反抵消恒等保留交换结合随意重排两个单身先混后拆lowbit分组。模板全体异或 → 得s若只有一个单身s即答案若有两个用s (-s)分组再异或。防坑a^a0只对偶数次成立s (-s)必须先保证s ≠ 0。 实际应用场景不止是刷题校验与纠错RAID奇偶校验、网络传输校验和加密一次性密码本OTP明文 ^ 密钥 ^ 密钥 明文差异检测两份配置/文件按块异或非零处即差异状态压缩权限位、开关集合用位掩码异或用来“翻转”某一位 今日思考题评论区见LC.137其余元素出现三次用“逐位统计mod3”是O(32n)用有限状态机是O(n)。如果元素出现k次k为任意整数逐位统计mod k的复杂度会变成多少它和有限状态机相比哪个更通用