难度: Easy
给你一个含 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) 的情况下解决这个问题吗? 你可以假定返回的数组不算在额外空间内。
运行时间: 38 ms
内存: 25.2 MB
class Solution:
def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
res = []
setNums = set(nums)
for i in range(1, len(nums) + 1):
if i not in setNums:
res.append(i)
return res
该题解的思路是先将原数组转换为集合，然后遍历从1到n的所有数字，检查每个数字是否在集合中。如果不在集合中，则说明该数字在原数组中消失，将其添加到结果数组中。最后返回结果数组。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
res = []
# 将原数组转换为集合
setNums = set(nums)
# 遍历从1到n的所有数字
for i in range(1, len(nums) + 1):
# 检查当前数字是否在集合中
if i not in setNums:
# 如果不在集合中，说明该数字在原数组中消失，将其添加到结果数组中
res.append(i)
return res
在该题解中，通过将原数组转换为集合来处理重复数字的问题。集合是一个不包含重复元素的数据结构，因此即使原数组中有重复的数字，它们在集合中只会被存储一次。这样，当我们遍历从1到n的数字检查它们是否在集合中时，我们实际上是在检查这些数字是否至少出现了一次。不在集合中的数字，即是那些在原数组中完全未出现过的数字，因此被认为是“消失”的数字。
这种方法在时间复杂度上是线性的，即O(n)，其中n是数组的长度。空间复杂度也是O(n)，因为需要额外的数据结构（集合）来存储数组中的元素。在极大的n值情况下，内存消耗可能成为问题，因为存储大量的数据需要相应大的内存空间。在极小的n值情况下，这个方法效率较高，因为操作的绝对时间和空间成本都非常低。关于优化，对于极大的数据集，可以考虑使用更节省空间的方法，例如原地修改数组（不使用额外的集合）来标记已存在的数字，这种方法可以将空间复杂度降低到O(1)。但这种优化会使得算法的理解和实现变得更复杂，因此是否采用取决于具体的应用场景和性能要求。