LeetCode 题解工作台
找到所有数组中消失的数字
给你一个含 n 个整数的数组 nums ，其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字，并以数组的形式返回结果。 示例 1： 输入： nums = [4,3,2,7,8,2,3,1] 输出： [5,6] 示例 2： 输入： nu…
2
题型
5
代码语言
3
相关题
当前训练重点
简单 · 数组·哈希·扫描
答案摘要
我们可以使用数组或哈希表记录数组中的数字，然后遍历 `[1, n]` 区间内的数字，若数字不存在于数组或哈希表中，则说明数组中缺失该数字，将其添加到结果列表中。 时间复杂度 ，空间复杂度 。其中 为数组长度。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
给你一个含 n 个整数的数组 nums ，其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字，并以数组的形式返回结果。
示例 1：
输入：nums = [4,3,2,7,8,2,3,1] 输出：[5,6]
示例 2：
输入：nums = [1,1] 输出：[2]
提示：
n == nums.length1 <= n <= 1051 <= nums[i] <= n
进阶：你能在不使用额外空间且时间复杂度为 O(n) 的情况下解决这个问题吗? 你可以假定返回的数组不算在额外空间内。
解题思路
方法一：数组或哈希表
我们可以使用数组或哈希表记录数组中的数字，然后遍历 [1, n] 区间内的数字，若数字不存在于数组或哈希表中，则说明数组中缺失该数字，将其添加到结果列表中。
时间复杂度 ，空间复杂度 。其中 为数组长度。
class Solution:
def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
s = set(nums)
return [x for x in range(1, len(nums) + 1) if x not in s]
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n) for a single pass through nums and an additional pass for collecting missing numbers. Space complexity ranges from O(n) using hash tables or counting arrays to O(1) using in-place marking, exposing trade-offs between memory usage and simplicity. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Expect a linear time solution without sorting.
- question_mark
Check if the candidate considers in-place marking to save space.
- question_mark
Look for clarity in handling duplicates and missing indices.
常见陷阱
外企场景- error
Incorrectly assuming all numbers appear exactly once, missing duplicates.
- error
Failing to handle the full range [1, n], especially the first or last elements.
- error
Using excessive memory or unnecessary sorting instead of direct scanning.
进阶变体
外企场景- arrow_right_alt
Return missing numbers in a sorted array instead of original order.
- arrow_right_alt
Find missing numbers when array contains numbers outside [1, n].
- arrow_right_alt
Handle streaming input where nums is too large to fit in memory at once.