leetcode-go/技巧/96-只出现一次的数字.md

tags, create time

tags	create time
技巧 位运算 异或 数组	2026-05-16 14:30

96-只出现一次的数字

题面

给你一个非空整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

要求：

• 线性时间复杂度 O(n)
• 常量额外空间 O(1)

示例 1：

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

示例 2：

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

示例 3：

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

---

思路

先思考一个问题 🤔

如果不用任何算法，你会怎么找到那个唯一的数字？

[!tip] 直觉方案 遍历数组，对每个数字统计出现次数，然后找出出现一次的——但这需要哈希表或排序，不满足 O(1) 空间的要求。

核心洞察：异或运算的性质 💡

回忆一下**异或（XOR）**的三条基本性质：

性质	表达式	含义
归零律	a ^ a = 0	相同数字异或为 0
恒等律	a ^ 0 = a	任何数与 0 异或等于自身
交换律 & 结合律	a ^ b ^ c = a ^ (b ^ c) = (a ^ c) ^ b	异或的顺序不影响结果

[!question] 启发式提问 如果一个数组中除了一个数字外，其余都恰好出现两次，把这些数字全部异或起来会发生什么？

根据归零律，每对相同的数字异或后变为 0；再根据恒等律，所有的 0 异或起来还是 0；最后剩下的就是那个只出现一次的数字！

流程演示

以 nums = [4, 1, 2, 1, 2] 为例：

flowchart LR
    A["开始: result = 0"] --> B["result ^= 4 → 4"]
    B --> C["result ^= 1 → 5"]
    C --> D["result ^= 2 → 7"]
    D --> E["result ^= 1 → 6"]
    E --> F["result ^= 2 → 4"]
    F --> G["result = 4 ✅"]

    style A fill:#e1f5fe
    style G fill:#c8e6c9

更直观的理解（利用交换律和结合律重新排列）：

4 \oplus 1 \oplus 2 \oplus 1 \oplus 2 = 4 \oplus (1 \oplus 1) \oplus (2 \oplus 2) = 4 \oplus 0 \oplus 0 = 4

[!info] 关键结论 不需要关心顺序——异或的交换律保证了无论成对的数字在数组中的位置如何，它们最终一定会被配对抵消。

---

代码提示

伪代码

初始化 result = 0
遍历数组中的每个数字 num:
    result = result XOR num
返回 result

复杂度分析

指标	结果	说明
时间复杂度	O(n)	只需遍历数组一次
空间复杂度	O(1)	只使用了一个变量 result

完美满足题目要求！

---

技巧

1. 异或找唯一元素的通用模式

[!summary] 模板记忆法

ans := 0
for _, v := range nums {
    ans ^= v
}
return ans

看到「除一个元素出现一次/奇数次外，其余出现偶数次」→ 优先考虑异或。

2. 异或的小应用清单

这些面试高频技巧都源于异或的相同两条性质：

应用场景	方法	核心原理
找唯一元素	全数组异或	a ^ a = 0, a ^ 0 = a
判断两个数是否相等	a ^ b == 0	相等则结果为 0
交换两个变量（经典面试题）	a ^= b; b ^= a; a ^= b	三步异或完成交换，无需临时变量
翻转指定位	num ^= mask	mask 中为 1 的位被翻转

3. 变体题延伸 🚀

题目	变化点	思路升级
136. Single Number（本题）	其余出现两次	直接全异或 ✅
137. Single Number II	其余出现三次	按位统计每个位上 1 的出现次数，%3 剩余的拼接
260. Single Number III	有两个只出现一次的数	先全异或得到 x ^ y，找最低位的 1 分组，再分别异或

[!note] 思考方向 当「其余元素出现 k 次」时，本质上是把逐位计数的模运算从 %2 推广到 %k。异或是最自然的 %2 计数器。

---

代码

// SingleNumber finds the element that appears exactly once
// while all other elements appear exactly twice.
func singleNumber(nums []int) int {
    // result 初始化为 0（异或的单位元）
    // 根据恒等律：a ^ 0 = a
    result := 0

    // 遍历所有数字，依次异或
    // 根据归零律：a ^ a = 0，成对的数字会相互抵消
    // 根据交换律：无论顺序如何，结果不变
    for _, num := range nums {
        result ^= num
    }

    // 此时 result 就是那个只出现一次的数字
    return result
}

Go 运行细节

[!example] Go 中异或运算符 Go 语言使用 ^ 作为按位异或运算符：

• 5 ^ 3 = 0b0101 ^ 0b0011 = 0b0110 = 6
• 注意区分逻辑异或 != —— 这里用的是按位异或