LeetCode 645. 错误的集合
目录
题目描述
题意分析
要什么：数组本应是
1..n的一个排列，但其中恰好有一个数被写成了另一个数的复制品，导致某个数出现两次、某个数一次都没出现。返回[重复的数, 缺失的数]。
约束透露的信号：元素取值被死死限制在1..n，而数组长度也正好是n——值域与下标域一一对应，这是这类题最重要的信号，它同时打开了三条路：用长度n+1的计数数组直接按值索引、把值当下标做原地标记从而做到 $O(1)$ 空间、或者用求和 / 异或的数学恒等式。返回值要求同时给出两个数，说明一次遍历应当能把两个信息一起收集，不必分两趟解两个独立问题。
边界：n最小为 2（要同时存在重复和缺失至少需要两个位置）；重复的数和缺失的数可以相邻也可以相隔很远，甚至重复的是 1、缺失的是n；数组顺序完全无序，不能假设任何有序性；返回顺序被规定为「先重复后缺失」，写反直接判错。
解法：计数数组
核心思路
暴力做法是对每个
1..n的候选值扫一遍数组数它出现几次，出现 2 次的是重复、0 次的是缺失，时间 $O(n^2)$。
瓶颈在于同一趟扫描只回答了「某一个值出现几次」这一个问题，而一次扫描其实可以把所有值的出现次数一起统计出来。
关键观察是值域已知且很小：所有元素都落在1..n，于是「值」可以直接当作数组下标使用，不需要哈希表这种通用但带常数开销的结构。
由此确定要维护的状态：cnt[v]表示值v在输入数组中出现的次数。因为原始数据是1..n的排列被改动了一处，所以统计完成后cnt必然恰好有一个位置为 2、一个位置为 0，其余全为 1——这条性质既是答案的来源，也是正确性的保证。第二趟从 1 扫到n时，看到 2 就记为重复，看到 0 就记为缺失，一趟同时拿到两个答案。
解题步骤
- 开一个长度为
n + 1的计数数组cnt。为什么是n + 1而不是n：值域是1..n，要让下标和值直接对齐就必须能容纳下标n，下标 0 空置不用；写成n会在遇到值n时越界。- 遍历输入，执行
cnt[x]++。为什么不用先判断范围：题目保证所有元素都在1..n内，可以放心直接索引；这也是「值域受限」这个条件真正兑现价值的地方。- 再从
i = 1遍历到n，cnt[i] == 2记为dup，cnt[i] == 0记为missing。为什么从 1 开始：下标 0 不对应任何合法值，它的计数恒为 0，若从 0 开始扫会立刻把missing误设成 0。为什么用else if：两个条件天然互斥，一个值不可能既出现 2 次又出现 0 次，写成else if更清晰也少一次比较。- 返回
[dup, missing]。为什么顺序不能颠倒：题目明确规定第一个元素是重复出现的那个数，第二个才是缺失的，这是纯粹的约定，没有推导余地。- 以
nums = [1, 2, 2, 4]走一遍。n = 4，cnt初始为[0, 0, 0, 0, 0]。第一趟统计：读到 1 使cnt[1] = 1，读到 2 使cnt[2] = 1，再读到 2 使cnt[2] = 2，读到 4 使cnt[4] = 1，最终cnt = [0, 1, 2, 0, 1]。第二趟从i = 1扫起：cnt[1] = 1两个条件都不满足，跳过；cnt[2] = 2命中重复，dup = 2；cnt[3] = 0命中缺失，missing = 3；cnt[4] = 1跳过。返回[2, 3]。反查一下：原数组应为[1,2,3,4]，3 被写成了 2，所以 2 重复、3 缺失，完全对得上。
代码实现
// 核心实现：计数数组，维护必要状态并避免重复处理。
class Solution {
public int[] findErrorNums(int[] nums) {
int n = nums.length;
int[] cnt = new int[n + 1];
for (int x : nums) {
cnt[x]++;
}
int dup = -1;
int missing = -1;
for (int i = 1; i <= n; i++) {
if (cnt[i] == 2) {
dup = i;
} else if (cnt[i] == 0) {
missing = i;
}
}
return new int[] {dup, missing};
}
}
// 核心实现：计数数组，维护必要状态并避免重复处理。
func findErrorNums(nums []int) []int {
n := len(nums)
count := make([]int, n+1)
for _, num := range nums {
count[num]++
}
dup, missing := -1, -1
for i := 1; i <= n; i++ {
if count[i] == 2 {
dup = i
} else if count[i] == 0 {
missing = i
}
}
return []int{dup, missing}
}
复杂度分析
- 时间复杂度：$O(n)$。凭什么：第一趟遍历输入
n次、每次做一次 $O(1)$ 的下标自增；第二趟遍历1..n共n次、每次两个常数比较，两趟相加仍是线性，没有排序也没有嵌套。- 空间复杂度：$O(n)$。凭什么：额外开了长度
n + 1的计数数组；这是本解法用空间换时间与可读性的代价，若必须做到 $O(1)$ 额外空间，可改用原地标记或数学法。
关键点总结
- 值域等于下标域时，数组就是最快的哈希表：把值直接当下标用，省掉哈希计算与装箱开销。看到「元素都在
1..n」这句话就该条件反射地想到这一族技巧（计数、原地取负标记、置换归位）。- 一次统计同时服务多个问题：本题的「重复」和「缺失」共享同一份计数结果，不要写成两个独立的查找。识别出「多个答案来自同一份中间状态」能显著简化代码。
- 不变量给了正确性保证：因为原始数据是排列且只被改动一处，统计结果必然是「一个 2、一个 0、其余全 1」，这句话让你不必担心找不到答案或找到多个答案。
- 面试视角：这题被问到时，$O(n)$ 时间 $O(n)$ 空间只是及格线，面试官几乎一定会追问「能否做到 $O(1)$ 额外空间」。要准备好两条后手——一是原地标记法（遍历时把
nums[|x|-1]取负，遇到已经是负数的就说明该值重复，第二趟找仍为正的位置即缺失）；二是数学法（实际和减理想和得到dup - missing，实际平方和减理想平方和得到dup² - missing²，两式联立解出两数）。- 返回值顺序、下标从 1 还是从 0 起，这类「约定型」细节在简单题里是主要失分点，写完务必用一个最小用例复核。
易错点总结
- 错误写法：计数数组开成
new int[n]；用例nums = [2, 2]→ 统计值 2 时访问下标 2 越界，直接抛数组越界异常。- 错误写法：第二趟从
i = 0开始扫；用例nums = [1, 2, 2, 4]→cnt[0]恒为 0，missing先被设成 0，虽然随后会被 3 覆盖，但若把条件写成「找到就 break」则直接返回[2, 0]。- 错误写法：返回
[missing, dup]；用例nums = [1, 2, 2, 4]→ 返回[3, 2]，正确答案是[2, 3]，纯粹的顺序错误。- 错误写法：把重复判定写成
cnt[i] > 1并用if/if而非else if，同时缺失判定写成cnt[i] < 1；用例 任意输入 → 逻辑虽等价但多做一次比较；真正的坑是有人顺手写成cnt[i] != 1一个分支同时处理两种情况，结果无法区分是 2 还是 0，两个答案混在一起。- 错误写法：只扫一趟，边统计边判断
cnt[x] == 2就返回；用例nums = [3, 2, 2, 4]→ 遇到第二个 2 时立刻返回，此时还没扫完数组，missing尚未确定，返回[2, -1]。- 错误写法：用「实际和减理想和」求出差值后直接当作
missing；用例nums = [1, 2, 2, 4]→ 实际和 9、理想和 10，差值是dup - missing = -1，这只是两数之差，不能单独解出任何一个，必须再配一个方程（如平方和）。- 错误写法：先排序再找相邻相等元素定位重复、找相邻差 2 的位置定位缺失，却忘记缺失可能在两端；用例
nums = [2, 2]→ 排序后没有「相邻差 2」的位置，缺失的 1 在最左端被漏掉，返回[2, -1]。- 错误写法：用原地取负标记但忘记取绝对值取值；用例
nums = [1, 2, 2, 4]→ 第一个 2 把nums[1]变成 -2，扫到第二个元素时读到 -2 当下标直接越界。- 错误写法：用
HashSet判重复、再另开循环从 1 到n查缺失，但用的是同一个已被污染的集合；用例nums = [2, 2]→ 集合里只有{2}，缺失查到 1 正确，但重复靠「add 返回 false」判定时若忘记记录会返回[-1, 1]。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 448. 找到所有数组中消失的数字 | 简单 | 只求缺失但可能有多个，原地取负标记法在这里是标准解而非可选项 |
| 442. 数组中重复的数据 | 中等 | 镜像问题，找的是全部重复项，要求 $O(1)$ 额外空间且不能破坏可恢复性 |
| 287. 寻找重复数 | 中等 | 明令禁止修改数组，只能把下标跳转看成链表用快慢指针找环入口 |
| 41. 缺失的第一个正数 | 困难 | 值域不再保证落在 1..n，需要先用置换把能归位的元素放回自己的位置 |