每日一题：每天一个新挑战；
循序渐进：从易到难，扎实掌握；
系统分类：按数据结构分类，有助于构建知识框架；
丰富题量：100 道精选题，覆盖简单/中等/困难难度。

给你一个含 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) 的情况下解决这个问题吗? 你可以假定返回的数组不算在额外空间内。

代码卡片

题目解析

给定一个长度为 n 的数组 nums，数组中的元素值范围在 [1, n] 之间。题目要求找出 [1, n] 范围内没有出现在 nums 中的所有数字，并以数组形式返回结果。

方法一：使用哈希表

可以通过哈希表来记录 nums 中出现过的数字。然后遍历 [1, n]，如果某个数字没有出现在哈希表中，就将其加入到结果数组中。

时间复杂度: O(n)，遍历了数组两次，一次是构建哈希表，另一次是查找未出现的数字。
空间复杂度: O(n)，使用了额外的哈希表存储出现过的数字。

var findDisappearedNumbers = function(nums) {
    const n = nums.length;
    const numSet = new Set(nums);
    const result = [];

    for (let i = 1; i <= n; i++) {
        if (!numSet.has(i)) {
            result.push(i);
        }
    }

    return result;
};

方法二：标记法（不使用额外空间）

如果要在不使用额外空间且时间复杂度为 O(n) 的情况下解决问题。可以通过对原数组进行标记的方法来实现。遍历数组中的每个数字，将数字 nums[i] 对应的位置上的值标记为负数，表示该位置对应的数字已经出现过。最后，再次遍历数组，凡是值为正数的位置，其对应的数字就是缺失的数字。

时间复杂度: O(n)，只遍历了数组两次。
空间复杂度: O(1)，除了返回值外，未使用额外的空间。

var findDisappearedNumbers = function(nums) {
    for (let i = 0; i < nums.length; i++) {
        const index = Math.abs(nums[i]) - 1;
        if (nums[index] > 0) {
            nums[index] = -nums[index];
        }
    }

    const result = [];
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] > 0) {
            result.push(i + 1);
        }
    }

    return result;
};