题目要求

给你一个非空整数数组 nums。

数组中只有一个元素出现一次，其余每个元素都恰好出现两次。题目要求返回那个只出现一次的元素。

LeetCode 提供的方法接口是：

singleNumber(nums: List[int]) -> int

除了返回正确答案，解法还需要满足两个要求：

  • 时间复杂度是 O(n)。
  • 只使用 O(1) 额外空间。

示例 1

输入：nums = [2,2,1]
输出：1

2 出现两次，只有 1 出现一次。

示例 2

输入：nums = [4,1,2,1,2]
输出：4

1 和 2 都能找到相同的另一个元素，最后只有 4 没有配对。

示例 3

输入：nums = [1]
输出：1

数组只有一个元素时，它就是答案。

约束

  • 1 <= nums.length <= 3 * 10^4
  • -3 * 10^4 <= nums[i] <= 3 * 10^4
  • 除一个元素只出现一次外，其余元素都恰好出现两次。

Step 1：先把“只出现一次”说准确

先看：

nums = [4,1,2,1,2]

在这个很小的数组里，我们可以用眼睛寻找相同的数字：

1 和 1 配成一对
2 和 2 配成一对
4 没有配对

所以答案是 4。

当前 baseline 是：

逐个寻找相同元素，把能够配对的数字排除掉。

这个 baseline 的 break 是：

人工观察只适合很小的输入。数组变长、相同元素彼此离得很远以后，我们还没有一个可以执行的过程来记录哪些数字已经找到配对。

这一步先不选择具体算法，只固定后面必须同时解决的两个问题：

  • 如何正确排除所有出现两次的元素？
  • 如何在 O(n) 时间、O(1) 额外空间内留下唯一元素？

现在这一版能做到：

  • 准确说明输入中“一个元素出现一次，其余元素出现两次”的保证。
  • 知道结果是未配对的那个元素。
  • 知道最终解法不能依赖随输入规模增长的额外存储。

它还缺：

  • 一个可以运行的配对过程。

Step 2：先用集合写出正确 baseline

当前 baseline 是：

逐个寻找相同元素，把能够配对的数字排除掉。

它的问题不是思路错误，而是还不能执行。数组中的两个相同元素可能相距很远，我们需要记住目前有哪些数字还没有找到配对。

在前一版上增加一个集合 seen：

from typing import List


def single_number_with_set(nums: List[int]) -> int:
    seen = set()

    for num in nums:
        if num in seen:
            seen.remove(num)
        else:
            seen.add(num)

    return next(iter(seen))

这里的循环 invariant 是：

处理完任意一个前缀后，seen 保存这个前缀中还没有完成配对的数字。

用 [4,1,2,1,2] 检查这个过程：

读到的数字操作seen
4没见过，加入{4}
1没见过，加入{4, 1}
2没见过，加入{4, 1, 2}
1已存在，删除{4, 2}
2已存在，删除{4}

题目保证最后只有一个数字没有配对，所以集合最终只剩答案。

运行检查：

assert single_number_with_set([2, 2, 1]) == 1
assert single_number_with_set([4, 1, 2, 1, 2]) == 4
assert single_number_with_set([1]) == 1
assert single_number_with_set([-1, 2, 2]) == -1

现在这一版能做到：

  • 对任意顺序的输入执行配对过程。
  • 在线性时间内找到唯一元素。
  • 通过具体 invariant 说明集合中为什么只剩答案。

它还缺：

  • 最坏情况下，seen 可能保存 O(n) 个数字，不满足 O(1) 额外空间要求。

Step 3：不保存配对，能不能让它们自己抵消

当前 baseline 是集合版本。它之所以需要额外空间，是因为每个尚未配对的数字都必须被保存。

现在的 break 很具体：

我们需要保留“相同数字最终会成对消失”这个效果，但不能真的存下这些数字。

这时才需要引入 XOR，也就是 Python 中的 ^ 运算。

它有四个与本题直接相关的性质：

x ^ x = 0
x ^ 0 = x
a ^ b = b ^ a
(a ^ b) ^ c = a ^ (b ^ c)

前两个性质说明相同数字能够抵消，后两个性质说明抵消不受原数组中相对位置影响。

不要只记性质，直接把它们用在 [4,1,2,1,2] 上：

4 ^ 1 ^ 2 ^ 1 ^ 2
= 4 ^ (1 ^ 1) ^ (2 ^ 2)
= 4 ^ 0 ^ 0
= 4

这里发生的事情与集合 baseline 一样：

  • 两个 1 消失。
  • 两个 2 消失。
  • 没有配对的 4 被保留下来。

区别是 XOR 不需要保存“哪些数字仍在等待配对”。整个抵消结果可以压缩进一个整数。

负数也仍然满足相同的代数性质：

-1 ^ 2 ^ 2
= -1 ^ 0
= -1

现在这一版能做到：

  • 实际使用 XOR 抵消任意位置上的重复元素。
  • 解释为什么元素顺序不会影响结果。
  • 把集合中的多个未配对状态压缩成一个整数结果。

它还缺：

  • 一个逐个读取数组元素的状态更新。
  • 对这个状态更新的循环 invariant。

Step 4：把抵消过程写成一个累加器

当前 baseline 已经知道整个数组应该计算：

nums[0] ^ nums[1] ^ ... ^ nums[n - 1]

现在只差把这个表达式变成一次扫描。

增加一个累加器：

answer = 0

每读取一个数字，就把它合并进当前结果：

answer ^= num

完整的 LeetCode 实现是：

from typing import List


class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        answer = 0

        for num in nums:
            answer ^= num

        return answer

循环 invariant 是：

每次迭代结束后，answer 等于当前已处理前缀中所有数字的 XOR 结果。

初始时还没有处理数字，空前缀的结果是 0。每轮执行 answer ^= num 后，新数字被纳入前缀结果，因此 invariant 继续成立。

循环结束时，前缀就是整个数组。所有出现两次的数字相互抵消，只出现一次的数字就是最终结果。

运行检查

solution = Solution()

assert solution.singleNumber([2, 2, 1]) == 1
assert solution.singleNumber([4, 1, 2, 1, 2]) == 4
assert solution.singleNumber([1]) == 1
assert solution.singleNumber([-1, 2, 2]) == -1

复杂度

  • 时间复杂度：O(n)。每个元素只参与一次 XOR。
  • 额外空间复杂度：O(1)。除 answer 外不使用随输入增长的存储。

常见错误

1. 使用集合后忽略空间要求

集合版本是正确 baseline，但它的最坏额外空间是 O(n)，不能作为最终答案。

2. 把 XOR 写成逻辑或

Python 的 XOR 运算符是 ^，不是 or，也不是 |。

3. 忘记题目的出现次数保证

这个解法依赖“其余元素都恰好出现两次”。如果元素可能出现三次，成对抵消模型就不再直接适用。

4. 用算术公式代替后仍声称 O(1) 空间

2 * sum(set(nums)) - sum(nums) 仍然创建了集合，因此额外空间不是 O(1)。

小结

这道题的推导路线是：

人工配对
-> 用集合记录未配对数字
-> 发现集合违反常量空间要求
-> 用 XOR 让重复元素自行抵消
-> 用一个累加器完成线性扫描

需要记住的不是一行代码，而是 XOR 在这里承担的状态压缩作用：它保留未配对结果，同时让所有重复对归零。

下一题可以做 LeetCode 191 Number of 1 Bits，继续学习如何用位运算直接修改二进制状态。