题目描述

给你一个含 n 个整数的数组 nums ，其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字，并以数组的形式返回结果。

示例 1：

1
2
输入：nums = [4,3,2,7,8,2,3,1]
输出：[5,6]

算法思路

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

如果可以利用额外空间，那么这个题目很简单，只需要先创建一个集合，将1~n所有数字加进去，再遍历nums，把所有存在的数字剔除掉就可以，然后返回集合的数组形式。

但是要求不能用额外空间我就没办法做了，只能看官方题解，题解思路比较奇怪，其使用了原地哈希表，也就是把nums本身当作哈希表进行操作，大体上是这样：

  1. 遍历nums[i]，由题意由$1 <= nums[i]<=n$，那么我们可以直接操作nums[nums[i]-1]，让其变为负数（只是做一个标记，代表nums[i]出现过）
  2. 再次遍历nums，如果nums[i]是正数，说明i+1没有出现过，添加到返回数组即可
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
        
        for n in nums:
            nums[abs(n)-1] = - abs(nums[abs(n)-1])
            #找到相应的鸽笼位置，取反

        res = []
        for i, v in enumerate(nums):
            if v >0:#如果大于0，说明没被占过，也就是没有出现过的数字
                res.append(i+1)

        return res

放一个python题解，cpp懒得写了。