LeetCode 题解工作台
错误的集合
集合 s 包含从 1 到 n 的整数。不幸的是，因为数据错误，导致集合里面某一个数字复制成了集合里面的另外一个数字的值，导致集合 丢失了一个数字 并且 有一个数字重复 。 给定一个数组 nums 代表了该集合发生错误后的结果。 请你找出重复出现的整数，再找到丢失的整数，将它们以数组的形式返回。 示例…
4
题型
6
代码语言
3
相关题
当前训练重点
简单 · 数组·哈希·扫描
答案摘要
我们用 表示 所有数字的和，用 表示数组 去重后的数字和，用 表示数组 的数字和。 那么 $s - s_2$ 就是重复的数字，而 $s_1 - s_2$ 就是缺失的数字。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
集合 s 包含从 1 到 n 的整数。不幸的是，因为数据错误，导致集合里面某一个数字复制成了集合里面的另外一个数字的值，导致集合 丢失了一个数字 并且 有一个数字重复 。
给定一个数组 nums 代表了该集合发生错误后的结果。
请你找出重复出现的整数，再找到丢失的整数，将它们以数组的形式返回。
示例 1：
输入：nums = [1,2,2,4] 输出：[2,3]
示例 2：
输入：nums = [1,1] 输出：[1,2]
提示：
2 <= nums.length <= 1041 <= nums[i] <= 104
解题思路
方法一：数学
我们用 表示 所有数字的和，用 表示数组 去重后的数字和，用 表示数组 的数字和。
那么 就是重复的数字，而 就是缺失的数字。
时间复杂度 ，空间复杂度 ，其中 是数组 的长度。需要额外的空间对数组去重。
class Solution:
def findErrorNums(self, nums: List[int]) -> List[int]:
n = len(nums)
s1 = (1 + n) * n // 2
s2 = sum(set(nums))
s = sum(nums)
return [s - s2, s1 - s2]
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n) because each element is scanned once or a constant number of times. Space complexity is O(n) if using a hash set, but can be reduced to O(1) with the bit manipulation or sum difference methods. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Expect an initial check for duplicates during array traversal.
- question_mark
Look for use of hash set or in-place marking to detect repeated numbers.
- question_mark
Confirm candidate recognizes missing number derivation using sum or XOR differences.
常见陷阱
外企场景- error
Overlooking that the array may not be sorted and assuming sequential indices.
- error
Double-counting elements or miscalculating the missing number after finding the duplicate.
- error
Using inefficient nested loops instead of O(n) scanning and hash tracking.
进阶变体
外企场景- arrow_right_alt
The array could contain multiple duplicates with multiple missing numbers, requiring generalized mapping.
- arrow_right_alt
Input array might be read-only, pushing the solution toward XOR or arithmetic methods.
- arrow_right_alt
Numbers could span a larger range with gaps, emphasizing the need for scalable hash-based scanning.