刷LeetCode中等题时137. 只出现一次的数字 II 算是比较经典的位运算和哈希表应用题目核心考点是「线性时间复杂度O(n)」和「常数级空间复杂度O(1)」这两个要求直接限制了我们不能用暴力解法也倒逼我们思考更高效的底层逻辑。今天就拆解这道题分享两种可行解法从易到难帮大家吃透这道题的核心思路。一、题目复盘明确核心需求先再看一遍题目避免理解偏差给你一个整数数组 nums 除某个元素仅出现一次外其余每个元素都恰出现三次。请你找出并返回那个只出现了一次的元素。关键约束必看时间复杂度必须是 O(n)意味着不能用嵌套循环比如双重for循环枚举只能遍历数组常数次1次、32次这类固定次数都算。空间复杂度必须是 O(1)意味着不能用额外的、随数组长度变化的空间比如长度为n的哈希表、数组都不行只能用固定数量的变量。补充数组中的元素可以是正数、负数这一点在第二种解法中需要特别注意不过代码已经处理好了后面会说。二、解法一哈希表统计频率易懂但不满足空间约束首先想到的最直观的解法就是用哈希表统计每个数字出现的次数然后遍历哈希表找到出现次数为1的数字。这种方法虽然简单易懂但空间复杂度是 O(n)不满足题目要求的「常数级空间」不过可以作为入门思路帮我们理解题目再过渡到最优解。1. 代码实现TypeScriptfunctionsingleNumber_1(nums:number[]):number{constfreqnewMap();// 第一步遍历数组统计每个数字的出现频率for(constnumofnums){// 若哈希表中已有该数字频率1否则初始化为1freq.set(num,(freq.get(num)||0)1);}letans0;// 第二步遍历哈希表找到频率为1的数字for(const[num,occ]offreq.entries()){if(occ1){ansnum;break;// 找到后直接退出提升效率}}returnans;};2. 思路解析核心逻辑利用哈希表的「键值对」特性键存数字值存该数字出现的次数。遍历数组nums对每个数字num更新其在哈希表中的频率不存在则为1存在则1。再遍历哈希表的entries找到值为1的键就是我们要找的「只出现一次的数字」。3. 优缺点分析优点代码简洁、思路直观几乎不需要思考底层逻辑适合新手入门调试也简单。缺点空间复杂度O(n)哈希表的空间会随着数组长度n的增加而增加不满足题目「常数级空间」的要求只能作为过渡解法。三、解法二位运算最优解满足所有约束这是这道题的核心解法也是面试中常考的思路。核心原理是「二进制位统计」—— 因为除了目标数字其余每个数字都出现3次那么对于二进制的每一位0~31位因为JavaScript/TypeScript中数字是32位有符号整数所有数字在该位上的1的总数要么是3的倍数全是出现3次的数字贡献要么是3的倍数1目标数字贡献了1。1. 代码实现TypeScriptfunctionsingleNumber_2(nums:number[]):number{letans0;// 遍历32位二进制的每一位0~31位for(leti0;i32;i){lettotal0;// 统计所有数字在第i位上的1的总数for(constnumofnums){// 右移i位将第i位移到最低位再与1按位与得到该位的值0或1total((numi)1);}// 若总数不能被3整除说明目标数字在该位上是1将该位设为1if(total%3!0){ans|(1i);}}returnans;};2. 思路拆解逐行理解不怕看不懂我们先明确一个前提32位二进制中每一位只有0和1两种状态而出现3次的数字其每一位的1都会被计算3次总和是3的倍数只有目标数字其某几位的1会被多计算1次导致该位的总和不能被3整除。逐行解析代码初始化ans0ans用来存储最终的目标数字初始值为0二进制全0。循环i从0到31遍历32位二进制的每一位从最低位到最高位。total0用来统计当前第i位上所有数字的1的总数。内层循环遍历nums对每个数字num计算其第i位是否为1——(num i) 1num i将num的二进制右移i位此时第i位会移动到最低位第0位。 1与1按位与若最低位是1结果为1若为0结果为0。这样就得到了num在第i位上的值。将所有num的第i位值相加得到total即该位上1的总数。判断total % 3 ! 0若总和不能被3整除说明目标数字在第i位上是1此时用ans | (1 i)将ans的第i位设为1。1 i将1的二进制左移i位此时只有第i位是1其余位是0。ans | …按位或运算将ans的第i位设为1不影响其他位。循环结束后ans就是只出现一次的数字。3. 关键细节为什么能处理负数有同学可能会问负数的二进制是补码会不会影响计算其实不需要额外处理因为代码中遍历了32位包括符号位对于负数的符号位第31位统计方式和其他位完全一致最终ans会自动还原为正确的负数。举个例子假设nums中有一个负数-4其32位补码的第31位是1其余相关位根据补码规则计算。统计时符号位的1会被计入total若total%3≠0ans的第31位会被设为1最终ans就是-4完全正确。4. 优缺点分析优点满足题目所有约束——时间复杂度O(n)外层循环32次内层循环n次总次数是32n属于O(n)空间复杂度O(1)只用到了ans、total、i三个固定变量是这道题的最优解也是面试重点考察的思路。缺点思路相对抽象需要对二进制位运算有一定了解新手可能需要多琢磨几遍才能吃透。四、两种解法对比刷题总结解法时间复杂度空间复杂度核心思路适用场景哈希表统计O(n)O(n)用哈希表记录频率找频率为1的数字新手入门、快速解题、不要求空间约束位运算O(n)O(1)统计每一位1的总数利用3的倍数特性定位目标数字面试、满足题目所有约束、底层逻辑考察刷题心得这道题的核心是「常数空间」的约束倒逼我们放弃直观的哈希表转向位运算。其实位运算的思路本质是「利用数字出现的次数规律通过二进制位的统计来剥离目标数字」这种思路在类似题目比如只出现一次的数字I、IV中也会用到。