1. 题目解析与核心思路leetcode第260题只出现一次的数字III是一道经典的位运算应用题。题目要求在一个整数数组nums中找出恰好出现一次的两个数字假设这两个数字为a和b其他所有数字都恰好出现两次。这与常见的找出唯一出现一次的数字问题不同之处在于本题需要处理两个独立的目标数字。1.1 问题特征分析首先我们需要明确几个关键特征数组中只有两个数字出现一次其余都出现两次时间复杂度要求O(n)空间复杂度要求O(1)不能修改原始数组虽然本题没有明确限制但这是这类问题的常见约束这些约束条件直接决定了我们不能使用哈希表等需要额外空间的解法也不能使用排序后遍历的O(nlogn)解法。位运算成为最合适的解决方案。1.2 位运算基础解决这个问题的关键在于理解异或(XOR)运算的几个重要性质任何数和0异或都是它本身a ^ 0 a任何数和自身异或都是0a ^ a 0异或运算满足交换律和结合律基于这些性质如果我们对整个数组进行异或运算最终结果将是a ^ b因为所有出现两次的数字都会相互抵消为0。2. 关键解题步骤详解2.1 获取区分位得到a ^ b后我们需要找到这两个数字的不同之处。因为a ≠ b所以a ^ b至少有一位是1。我们可以通过以下方法找到最右边的不同位diff xor (-xor)这里利用了补码的特性-xor是xor的补码加1这样操作可以得到xor中最右边的1所在的位置。这个diff值将成为我们区分a和b的关键。2.2 分组异或有了diff后我们可以根据这个位是否设置来将数组分成两组该位为1的数字该位为0的数字a和b必然分别位于这两组中因为这是它们不同的位。同时相同的数字一定会被分到同一组。然后我们对这两组分别进行异或运算最终得到的两个结果就是a和b。2.3 完整代码实现def singleNumber(nums): # 第一步得到a ^ b xor 0 for num in nums: xor ^ num # 第二步找到最右边的不同位 diff xor (-xor) # 第三步分组异或 a, b 0, 0 for num in nums: if num diff: a ^ num else: b ^ num return [a, b]3. 复杂度分析与优化3.1 时间复杂度该算法进行了三次线性遍历第一次遍历计算整体异或第二次遍历计算diff第三次遍历分组异或虽然看起来是O(3n)但常数系数可以忽略因此时间复杂度为O(n)满足题目要求。3.2 空间复杂度只使用了固定数量的额外变量(xor, diff, a, b)因此空间复杂度为O(1)也满足要求。3.3 可能的优化实际上我们可以将第一次和第三次遍历合并减少一次遍历def singleNumber(nums): xor 0 for num in nums: xor ^ num diff xor (-xor) a 0 for num in nums: if num diff: a ^ num return [a, a ^ xor]这样优化后只需要两次遍历但时间复杂度仍然是O(n)。4. 常见问题与调试技巧4.1 为什么使用diff xor (-xor)这是获取数字最右边1位的经典位操作技巧。例如假设xor 6 (二进制110)-xor的二进制表示是补码先取反得001再加1得010110 010 010 (即2)这样就得到了最右边的1所在的位置。4.2 如何处理负数这个算法对负数同样有效因为Python中的整数是以补码形式存储的位运算对正负数都适用。例如输入[-1,-1,-2,-3]异或结果为-2 ^ -3 1diff 1 -1 1分组后得到-2和-34.3 边界情况测试需要测试的边界情况包括最小数组[0,1]包含负数的情况最大数字和最小数字组合所有数字都是正数或都是负数的情况5. 位运算解题的通用思路这类找出出现一次的数字问题通常都可以用异或运算解决解题的一般步骤是分析题目中数字出现次数的规律考虑如何用位运算的性质来区分目标数字设计分组策略将目标数字分开分别处理各组得到最终结果对于更复杂的问题如所有数字出现三次只有一个出现一次则需要设计更复杂的位操作策略可能需要记录每位出现1的次数等。6. 同类题目推荐掌握了这道题的解法后可以尝试以下类似题目136.只出现一次的数字基础版137.只出现一次的数字II进阶版645.错误的集合变形题268.丢失的数字变种题这些题目都能帮助你巩固位运算解题的技巧特别是异或运算在各种场景下的灵活应用。