0448.md

title	description	keywords
448. 找到所有数组中消失的数字	LeetCode 448. 找到所有数组中消失的数字题解，Find All Numbers Disappeared in an Array，包含解题思路、复杂度分析以及完整的 JavaScript 代码实现。	LeetCode 448. 找到所有数组中消失的数字 找到所有数组中消失的数字 Find All Numbers Disappeared in an Array 解题思路 数组 哈希表

448. 找到所有数组中消失的数字

🟢 Easy  🔖  数组 哈希表  🔗 力扣 LeetCode

题目

Given an array nums of n integers where nums[i] is in the range [1, n], return an array of all the integers in the range [1, n] that do not appear in nums.

Example 1:

Input: nums = [4,3,2,7,8,2,3,1]

Output: [5,6]

Example 2:

Input: nums = [1,1]

Output: [2]

Constraints:

• n == nums.length
• 1 <= n <= 10^5
• 1 <= nums[i] <= n

Follow up: Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.

题目大意

给你一个含 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.length
• 1 <= n <= 10^5
• 1 <= nums[i] <= n

进阶： 你能在不使用额外空间且时间复杂度为 O(n) 的情况下解决这个问题吗? 你可以假定返回的数组不算在额外空间内。

解题思路

为了在 O(n) 时间复杂度和 O(1) 空间复杂度的条件下解决这个问题，我们可以利用数组的原地修改来标记已经出现过的数字。具体来说，利用数组元素值的符号来标记已经出现的数字，从而避免使用额外空间。

1. 数组 nums 中的每个元素都在 [1, n] 区间内，可以通过将数组元素 nums[i] 的值作为数组的索引来表示该数字是否出现过。
2. 遍历数组 nums，对于每个元素 num，将对应的索引 num - 1 位置的值变为负数，这样可以标记该位置对应的数字已经出现。
3. 最后，遍历数组 nums，查找所有值为正数的元素，它们的索引对应的数字就是没有出现过的数字。

复杂度分析

• 时间复杂度：O(n)。遍历数组两次，每次遍历的时间复杂度是 O(n)。
• 空间复杂度：O(1)。只使用了常数空间来存储结果数组 result，不需要额外的空间。

代码

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var findDisappearedNumbers = function (nums) {
	let result = [];

	// 标记出现过的数字
	for (let i = 0; i < nums.length; i++) {
		let num = Math.abs(nums[i]);
		if (nums[num - 1] > 0) {
			nums[num - 1] = -nums[num - 1]; // 将对应位置标记为负
		}
	}

	// 查找未出现的数字
	for (let i = 0; i < nums.length; i++) {
		if (nums[i] > 0) {
			result.push(i + 1); // 将未出现的数字加入结果
		}
	}

	return result;
};

相关题目

题号	标题	题解	标签	难度	力扣
41	缺失的第一个正数	[✓]	数组 哈希表	🔴	🀄️ 🔗
442	数组中重复的数据	[✓]	数组 哈希表	🟠	🀄️ 🔗
1980	找出不同的二进制字符串	[✓]	数组 哈希表 字符串 1+	🟠	🀄️ 🔗
2195	向数组中追加 K 个整数		贪心 数组 数学 1+	🟠	🀄️ 🔗
2295	替换数组中的元素		数组 哈希表 模拟	🟠	🀄️ 🔗
2554	从一个范围内选择最多整数 I	[✓]	贪心 数组 哈希表 2+	🟠	🀄️ 🔗
2557	从一个范围内选择最多整数 II 🔒		贪心 数组 二分查找 1+	🟠	🀄️ 🔗