企业官网建设流程全解析

LeetCode-Go 题解：268. Missing Number（缺失数字）—— 线性时间异或算法的源码级解析

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go

导读

本文围绕 LeetCode 第 268 题「Missing Number（缺失数字）」展开，以 leetcode/0268.Missing-Number/README.md 为核心骨架，并结合 LeetCode-Go 仓库中该题的 Go 实现与测试用例，深入讲解如何利用异或（XOR）性质在O(n) 线性时间复杂度、O(1) 常数额外空间内找出缺失数字。读完本文，你将掌握异或抵消法的推导过程、Go 实现细节、边界情况处理，以及如何在本仓库中运行测试验证结果。

1. 题目描述

Given an array containing n distinct numbers taken from0, 1, 2, ..., n, find the one that is missing from the array.

给定一个包含n个互不相同的数字的数组，这些数字取自0, 1, 2, ..., n，找出数组中缺失的那个数。

示例 1：

Input: [3,0,1] Output: 2

示例 2：

Input: [9,6,4,2,3,5,7,0,1] Output: 8

注意：你的算法应该具有线性时间复杂度。你能否只使用额外常数空间来实现？

2. 题目大意

给定一个包含0, 1, 2, ..., n中n个数的序列，找出0 .. n中没有出现在序列中的那个数。算法应该具有线性时间复杂度，并且只能使用额外常数空间。

这里需要特别留意两点约束：

1. 线性时间复杂度：即 O(n)，意味着不能使用双重循环暴力查找，也不能依赖排序（基于比较的排序至少 O(n log n)）；
2. 常数额外空间：意味着不能引入与 n 线性相关的辅助数组或哈希表。

这两条约束直接排除了"排序后逐位比对"与"哈希集合补集"两类直观解法，指引我们走向位运算。

3. 解题思路：利用异或性质 X^X = 0

要求找出0, 1, 2, ..., n中缺失的那个数。这里利用异或的性质：X^X = 0，即同一个数字与自己异或的结果为 0。

我们需要构造一个 X，用数组下标就可以了。数字下标是从[0, n-1]，数字是[0, n]，依次把数组里面的数字进行异或，把结果和n再异或一次，中和掉出现的数字，剩下的那个数字就是之前没有出现过的、缺失的数字。

3.1 为什么异或可行

异或运算满足三条关键性质：

• 交换律：a ^ b = b ^ a；
• 结合律：(a ^ b) ^ c = a ^ (b ^ c)；
• 自反性（抵消）：a ^ a = 0，且a ^ 0 = a。

现在考虑完整集合[0, 1, 2, ..., n]（共 n+1 个数）与数组nums（共 n 个数，缺失了其中一个）。若我们把这两组数全部异或在一起：

• 凡是同时出现在两个集合中的数，都会因X^X = 0被抵消；
• 唯一"落单"的那个数，就是缺失的数字。

但完整集合并不需要我们显式构造——数组下标天然就覆盖了[0, n-1]，而完整集合中比下标多出来的那个数正是n本身。因此：

result = 0 for i in 0..n-1: result ^= i // 下标部分，覆盖 0..n-1 result ^= nums[i] // 数组中的数字 result ^= n // 补上 n

最终result即为缺失的数字。

3.2 复杂度分析

• 时间复杂度：O(n)，只需一次线性遍历；
• 空间复杂度：O(1)，只使用了一个整型变量xor。

两项指标均严格满足题目的要求。

4. 仓库源码实现解析

本仓库的 Go 实现位于 leetcode/0268.Missing-Number/268. Missing Number.go，完整代码如下：

package leetcode func missingNumber(nums []int) int { xor, i := 0, 0 for i = 0; i < len(nums); i++ { xor = xor ^ i ^ nums[i] } return xor ^ i }

4.1 逐行剖析

• 第 3 行：初始化xor = 0（异或的零元，x ^ 0 = x），并声明循环变量i；
• 第 4-6 行：在单次循环内一次性完成xor ^ i ^ nums[i]，把下标与数组元素同时异或进结果。这里i的取值区间是[0, n-1]，nums[i]是数组中的 n 个数字；
• 第 8 行：循环结束后i == len(nums) == n，return xor ^ i等价于补上数字n的异或。

4.2 用一个示例走一遍

以nums = [3, 0, 1]（n = 3）为例：

最终返回 2，与题目示例 1 的输出一致。整个过程中出现过的{0, 1, 3}均被抵消，剩下唯一未出现的2。

4.3 为什么仓库实现如此简洁

从源码结构看，missingNumber没有做任何边界特判：当数组为空（n = 0）时，循环不执行，直接返回0 ^ 0 = 0，即唯一缺失的数字 0，行为依然正确。这正是位运算方案"无状态、无分支"的特点，也是它比数学求差法（n*(n+1)/2 - sum，存在整数溢出风险）在工程上更稳健的原因。

5. 测试用例验证

本仓库为每题都配有同名测试文件，本题的测试位于 leetcode/0268.Missing-Number/268. Missing Number_test.go。测试代码采用仓库统一的question268 / para268 / ans268结构组织：

package leetcode import ( "fmt" "testing" ) type question268 struct { para268 ans268 } // para 是参数 // one 代表第一个参数 type para268 struct { s []int } // ans 是答案 // one 代表第一个答案 type ans268 struct { one int } func Test_Problem268(t *testing.T) { qs := []question268{ { para268{[]int{3, 0, 1}}, ans268{2}, }, { para268{[]int{9, 6, 4, 2, 3, 5, 7, 0, 1}}, ans268{8}, }, } fmt.Printf("------------------------Leetcode Problem 268------------------------\n") for _, q := range qs { _, p := q.ans268, q.para268 fmt.Printf("【input】:%v 【output】:%v\n", p, missingNumber(p.s)) } fmt.Printf("\n\n\n") }

测试覆盖了两组数据：

1. [3, 0, 1]→ 期望输出 2（对应题目示例 1，n = 3，缺失 2）；
2. [9, 6, 4, 2, 3, 5, 7, 0, 1]→ 期望输出 8（对应题目示例 2，n = 9，缺失 8）。

从仓库整体来看，README_zh.md 宣称所有题解均达到100% test coverage，且gotest.sh脚本通过go test -covermode=atomic -coverprofile=coverage.txt ./leetcode/...对全部 leetcode 包统一收集覆盖率，本题目所在的 leetcode 包同样包含在这一统计范围内。

6. 在仓库中运行与验证

6.1 单独运行本题测试

在仓库根目录执行：

go test -v -run Test_Problem268 ./leetcode/

-v会输出测试过程中的【input】/【output】打印，可以直接对照题目示例核对结果。

6.2 运行全部题解测试并生成覆盖率

仓库根目录的 gotest.sh 提供了统一验证入口：

bash gotest.sh

脚本会以atomic覆盖模式对整个leetcode目录执行测试并产出coverage.txt。Go 版本要求为 1.19+（见仓库根目录 go.mod）。

7. 同类思路延伸

异或抵消法不是本题的唯一解法，但它是满足"线性时间 + 常数空间"双约束下最优雅的一种。其他常见思路对比：

异或方案同时规避了整数溢出与额外空间两个隐患，这也是 LeetCode-Go 仓库采用它的原因。

小结

本题的核心收获在于：当题目要求"线性时间 + 常数空间"时，优先考虑位运算。利用X^X = 0的自反性，以数组下标补全完整区间，即可在一次遍历中定位缺失元素。仓库中 268. Missing Number.go 仅用 6 行代码就实现了这一思路，配合 268. Missing Number_test.go 的用例，构成了一个完整、可验证的最小题解单元，可直接作为面试中该题的标准答案模板。

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go