你是不是也有过这样的经历刷题打卡群里有人贴了一道“只出现一次的数字”配了一句“一行代码搞定”评论区一群人追问为什么。我第一次看到这题时也觉得奇怪一个数组里其他数字都出现两次只有一个是单数按说难度不高怎么大家聊得这么兴奋后来自己把三种解法都写了一遍才意识到这题的含金量不在题目本身而在于它把位运算从“背公式”变成了“想通原理”。“只出现一次的数字”是LeetCode第136题很典型的数组加位运算题目。给定一个非空整数数组除了某个元素只出现一次外其余每个元素都恰好出现两次要求找出那个落单的元素。这题在技术面试里出场率很高一来约束明确最好在线性时间内解决并且不占用额外空间二来它的最优解只有几行代码但能看出你是不是真的懂异或运算。每天刷一题遇到这种题目值得多花十分钟做三件事一题多解、复杂度分析、追问变体。这篇博文就把这套完整做法连同我踩过的坑一次性讲清楚。1. 每天刷一道题为什么先选“只出现一次的数字”1.1 这道题到底在考察什么先看题面。一个非空整数数组 nums除了某个元素只出现一次其余每个元素都出现两次找出那个只出现一次的元素。很多人读题时忽略了“恰好出现两次”这个条件直接套哈希表虽然也能过但错过了题目真正想教的东西。这里的关键是“成对出现”这四个字它暗示了一个更强的数学性质相同数字可以互相抵消。这道题主要考察三个点。第一能不能快速给出一种可行解哈希表是最容易想到的第二能不能把额外空间降到 O(1)这需要跳出现有思路第三知不知道异或运算满足交换律和结合律。大多数算法题考的是“你会不会某个技巧”这题考的是“你愿不愿意在暴力解之外多想一步”。我在面试时习惯先讲哈希表然后话锋一转说“但其实还有一个空间 O(1) 的做法”面试官通常都会眼睛一亮。1.2 每日一题真正要建立的能力每天刷一道题真正的收获不是“我做过这道题”而是“我看到类似的模式能立刻反应”。拿这题来说它建立了一个非常典型的识别模式数组里的数字成对出现目标只有一个落单的。看到成对出现优先考虑异或看到多数出现但目标比较少考虑按位统计看到需要分组处理的考虑异或后按某一位分组。这些模式一旦形成条件反射后面遇到137题、260题、268题都会轻松很多。换句话说每日一题不是在收藏题解而是让大脑形成“问题特征到解法”的映射链。只出现一次的数字就是映射链路最短的一题非常适合作为位运算专题的起点。我见过很多刷题打卡坚持不下去的人问题不在数量而在题目之间没有关联每天都是孤零零的一道题今天二分明天动态规划知识点串不起来。把这题吃透再搭配两道升级题一周内就能体会到“举一反三”的爽感。2. 三种解法逐个拆哈希表、排序、异或2.1 哈希表方案最稳妥也是面试的第一步先把最简单的做出来。遍历数组用哈希表统计每个数字出现的次数最后返回次数为1的那个。代码很直白from collections import Counter def singleNumber(nums): counter Counter(nums) for key, value in counter.items(): if value 1: return key return None这种写法思路清晰但空间复杂度是 O(n)因为要存所有数字的出现次数。如果题目不要求 O(1) 空间这个解法完全合格。面试时不用一上来就憋最优解先讲一个能跑的再逐步优化反而显得思路有层次。哈希表还有一个变种把所有不同数字放进集合sum(set) 乘 2 减去原始数组总和也能得到落单数字。这个变种虽然代码更短但很容易栽在整型溢出上大数相减在某些语言里会越界所以我认为最稳的还是计数器或者直接用异或。2.2 排序方案不用额外空间但要付出时间代价如果题目没有严格要求 O(n)也可以先排序再两两比较。排序之后成对的数字必然相邻落单的那个会导致配对错乱。def singleNumber(nums): nums.sort() for i in range(0, len(nums) - 1, 2): if nums[i] ! nums[i 1]: return nums[i] return nums[-1]这个方案的时间复杂度是 O(n log n)因为排序占了大头。它有个隐藏问题排序会修改原数组。如果面试里明确要求不能改动入参这个解法直接废掉。另外循环跳步时要小心边界条件数组长度为奇数如果前面元素都成对最后一个就是答案如果循环里发现相邻两个不一样那个较前的就是落单数字。手动拿 [1, 1, 2, 3, 3] 跑一遍很快就能理解配对错位是怎么发生的。我个人认为排序解法最大的价值在于作为“时间和空间的取舍”讨论素材面试官可以顺势问你“能不能在 O(n) 时间 O(1) 空间内完成”引出真正的重点。2.3 异或方案几行代码解决这才是这题的灵魂第三种解法就是位运算中的异或代码非常短def singleNumber(nums): result 0 for num in nums: result ^ num return result原理基于异或的三条性质。第一任何数和自身异或结果为 0也就是 x ^ x 0第二任何数和 0 异或等于它自己也就是 x ^ 0 x第三异或运算满足交换律和结合律这意味着连续异或的先后顺序完全不影响最终结果。把数组里所有数字连续异或一遍出现两次的数字会两两抵消成 0最后剩下的就是只出现一次的那个数字。时间 O(n)空间 O(1)不看答案的话很难想到这条路。为什么这个解法能成立往深一层看是因为异或天然是“可逆”的。它在二进制层面检测的是“两个位是否不同”同一位置上两个相同数字的位必然一样异或结果为 0等于把这个贡献从总量里清除掉了。很多算法题的暴力解法之所以不够好是因为没有利用数据分布里的结构而这题的结构恰恰是“每个元素出现偶数次”。异或解法把这种结构利用得干干净净。刷题时如果你能自己推导出这个方案说明你已经理解了异或的数学本质而不只是会调 API。3. 异或运算的细节以及面试里容易被追问的三个点3.1 为什么异或能把相同数字抵消异或运算看的是二进制位两个数在同一位置上的位相同则结果为 0不同则为 1。比如 5 的二进制是 1013 的二进制是 0115 ^ 3 得到 110也就是十进制 6。当两个相同数字异或时每一个二进制位都相同结果所有位都是 0所以得到 0。这就是“成对抵消”的数学基础。拿一个具体例子手动跑一遍。假设 nums [2, 4, 2, 1, 1]初始 result 00 ^ 2 22 ^ 4 66 ^ 2 44 ^ 1 55 ^ 1 4最终结果 4正好是那个落单的数字。如果把每一步都写成二进制010^ 100 110 ^ 010 100整个过程非常直观两个 2 在第 1 步和第 3 步分别出现但它们不在相邻位置异或的顺序不影响抵消这就是交换律在起作用。建议新手都在纸上这样画一遍画完就再也不会忘了。3.2 负数参与异或会怎样面试官很喜欢追问如果数组里有负数这套解法还成立吗答案是成立。在绝大多数语言里整数按补码存储负数参与异或时逐位运算性质完全不变。比如 -2 ^ -2 依然等于 0-2 ^ 0 依然等于 -2。任何数和自身异或归零和 0 异或不变这两条对负数同样适用。不过 Python 这里有个小地方容易让人困惑bin(-2) 的输出是 -0b10很多人以为 Python 里负数只有两位二进制其实那只是显示方式Python 的位运算仍按补码处理。C/C、Java、Python 都没有问题。真正要小心的是 JavaScript它的位运算会把操作数先转成 32 位有符号整数超过这个范围的整数参与位运算时可能丢失精度不过这类题目的输入通常不会那么夸张。面试时谈到负数只需要说“补码表示下异或的数学性质不依赖数值符号所以成立”基本就能过关。3.3 三个容易踩的坑第一个坑是空数组。题目声明非空但防御性写法可以加一行判断返回 None 或者抛出异常避免线上环境出现 NPE 这类问题。第二个坑是只有一个元素。异或循环天然支持这种情况直接返回该元素就可以但如果用排序方案循环边界就要格外小心len(nums) - 1 在长度为 1 时是 0range(0, 0, 2) 为空循环后面要正确地返回 nums[-1]。第三个坑是运算优先级。异或运算的优先级低于加减法高于位与混写时容易出问题。我见过有人写 result num ^ 2本意是让 result 和 num 异或后加 2实际执行顺序却是 result 加 num 后再异或 2结果完全变了。写位运算表达式时该加括号的地方别偷懒。4. 两道升级题出现三次怎么办、两个落单的怎么办4.1 升级一其他数字都出现三次把“成对出现”改成“每三个出现一次”异或就失效了。原因很直接三个相同数字异或的结果是它本身不是 0抵消不干净。这时候需要用按位统计的思路。统计所有数字在某个二进制位上 1 的个数如果这个数量是 3 的倍数说明落单数字的这一位是 0否则就是 1。def singleNumber(nums): result 0 for i in range(32): count 0 for num in nums: count (num i) 1 if count % 3 1: result | (1 i) return result if result 2**31 else result - 2**32这段代码里下标 i 表示第几位count 统计该位上 1 的出现次数。因为其余数字都出现三次某个位上的 1 的个数要么是 3 的倍数要么是 3 的倍数加 1加 1 的情况只可能来自落单数字。最后需要处理一下最高位Python 整数没有固定位数手动把超过 2^31-1 的结果转成负数才能和题目要求的范围一致。这个解法的时间复杂度是 O(32n)仍然是线性空间 O(1)是 137 题的标准答案。4.2 升级二要找两个只出现一次的数字如果数组改成“有两个数字只出现一次其余都出现两次”做法就更巧妙了。先整体异或一遍得到的是两个落单数字的异或值 x ^ y。因为 x 和 y 不相等x ^ y 的结果里至少有一个二进制位是 1这个位就是它们俩的区别所在。找到最低的那个为 1 的位把数组按这一位分成两组同组内其余数字仍然成对再对每一组分别异或就能得到两个答案。def singleNumbers(nums): xor_all 0 for num in nums: xor_all ^ num lowbit xor_all (-xor_all) a b 0 for num in nums: if num lowbit: a ^ num else: b ^ num return a, b这段代码里 lowbit 的写法是一个高频技巧x (-x) 可以取出 x 二进制中最低位的 1。比如 12 的二进制是 1100取最低位的 1 后得到 4。如果这一行还不熟建议在纸上把 12 和 -12 的补码写出来逐位做与运算几步就能看懂。分组的核心逻辑是x 和 y 在这个位上一个为 0 一个为 1所以一定被分到不同组其他成对出现的数字在同一个组里也是成对的异或后互相抵消。这个方法对应 260 题是异或应用的经典套路。4.3 为什么要做升级题一道题如果只会背答案面试官稍微变一下就会卡住。反过来当你能从 136 题推导出 137 和 260 题的解法说明你不是在背题而是真的掌握了位运算的底层逻辑。每日一题如果能再走一步自己出两个变形题刷题效率会高很多。我给的建议是把这三题当成一个学习单元放在同一周内集中做掉。每做完一题就回头对比一次思考“上一题的方法为什么失效”“这一题需要补充什么新技巧”。这样串起来之后成对抵消、按位统计、分组异或这三个思路会同时刻在脑子里以后面试遇到位运算题你的起点就不是零了。5. 刷题心得与避坑清单5.1 一题多解是性价比最高的刷题方式同一个题目第一遍用哈希表第二遍用排序第三遍用异或每一遍都能学到不同的东西。哈希表练的是数据结构选型排序练的是边界条件异或练的是数学性质。三道解法都写一遍你对这题的认知就不再是“一道题”而是一个完整的方法论。我在刷题群里见过不少人直接抄最优解跳过前两种结果过两周连异或代码都写不出来因为没有推导过程记忆不牢。正确姿势是先拿到可行解再问“能不能更好”逼自己完成优化链路。5.2 草稿纸手动模拟的力量位运算这种东西只看代码很难内化。我建议每个新手至少手写一遍 2 ^ 4 ^ 2 的二进制过程步骤已经写在前面了照着画一遍就行。这个过程花不了三分钟但会让你真正记住“成对抵消”是怎么发生的。做升级题时也一样把数组分组、异或的每一步画出来思路会清晰很多。手动模拟看起来慢实际上是把日后调 bug 的时间省下来了。我每次遇到新的位运算技巧第一件事就是找张白纸写二进制写完再敲代码几乎从不需要调试。5.3 常见错误速查表下面这张表是我实际刷题时踩过、或者见同学踩过的坑整理成速查表放在手边比临时翻文档有用得多。错误类型典型表现解决办法空间超限用哈希表在 O(n) 空间下强行提交改用异或空间 O(1)修改原数组sort 破坏了入参确认题目是否允许否则换解法边界错误只有 1 个元素 / 空数组循环前判断或利用异或天然特性溢出问题集合求和中大数相减优先异或避免加减法优先级问题位运算表达式中括号缺失一行只做一件事混写时加括号符号问题Python 最高位没转负数结果超过 2^31-1 时手动处理这张表里最容易被忽略的是最后一行Python 刷题时很多人会忘记 int 是无固定位数的按位统计解法里需要手动判断第 31 位。建议做完题之后顺手把语言相关的边界情况也写进注释里面试时能主动提出来反而是加分项。5.4 积累一份自己的位运算工具箱碰到这题以后建议顺带整理几个常见位运算技巧之后刷题会频繁用到。n (n - 1) 可以清除最低位的 1常用于判断 2 的幂n (-n) 可以提取最低位的 1分组异或就靠它n ^ n 0 和 n ^ 0 n 是异或的归零和恒等性质n i 1 可以取出第 i 位是按位统计的基础。每一个技巧都对应一个经典题目比如判断 2 的幂、统计汉明距离、子集枚举慢慢就会形成自己的工具库。最后再分享一个小技巧136、137、260 这三道题是一个完整的学习单元放在同一个刷题周期里效果最好。我当初连着三天每天只做一道到第三天写 260 时几乎没有看题解因为前两天积累的“异或抵消”和“按位分组”思路已经自然串起来了。你也试试把这三题集中消化一周感受一下从单点突破到成体系掌握的差别这个过程比单刷十道孤立题要值太多了。