题目

给你一个含 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 <= 105
1 <= nums[i] <= n

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/find-all-numbers-disappeared-in-an-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法

本来用暴力破解，直接推导式生成一个从1到nums长度+1的list，如果在nums则不添加，但是吧，超时了。

class Solution:
    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
        return [i for i in range(1, max(nums) + 1) if i not in nums]

本来是想用求差的，但是list没这个方法，但是set有，所以换成set试一下。

class Solution:
    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
        return list(set(range(1, len(nums) + 1)).difference(set(nums)))

虽然过了，但是这个方法并不符合进阶。

秒呀法

这个空间虽然小了，但是时间就长了。
文字描述一下就是，既然给的list里面是1-n的数字，但是少了几个。
如果把这些数字-1，那么就是一个下标，可以把这个下标的值取反，或者加至不存在于nums中的值，当遍历一过次后，那些不存在于nums中的值的下标的值不会被改变。在最后返回的时候排除掉被改变的值就行了。
取反

class Solution:
    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
        for i in nums:
            t = abs(i) - 1
            if nums[t] > 0:
                nums[t] = -nums[t]
        return [index + 1 for index, value in enumerate(nums) if value > 0]

加上n

class Solution:
    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
        n = len(nums)
        for i in nums:
            nums[(i - 1) % n] += n
        return [index + 1 for index, value in enumerate(nums) if value <= n]