原地哈希表：力扣448. 找到所有数组中消失的数字

1、题目描述：

2、题解：

方法1：哈希集合法（不满足空间复杂度的要求）
思路：先把原数组放在哈希集合中，然后遍历[1,n]，n为数组的长度，把所有不在哈希集合中的数字添加找res中。
代码如下：

class Solution:
    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
        #哈希表法之哈希集合,
        hashset = set(nums)
        res = []
        for i in range(1,len(nums) + 1):
            if i not in hashset:
                res.append(i)
        return res

方法2：原地哈希表法：
相同思路的题，可以对比记忆：
牛客-剑指offer系列题解:数组中重复的数字（提供了三种方法）
原地哈希表：力扣41. 缺失的第一个正数
原地哈希表：力扣442. 数组中重复的数据
思路1：

原数组操作，先遍历一遍数组，令其值-1为索引的 所在数组中的元素+len(nums)
然后，再次遍历，把数组中的值小于len(nums)的下标+1，添加到res中

如图：遍历数组，先构建原地哈希表；然后再次遍历数组，如果 nums[i]小于n（n为数组长度），说明构建原地哈希的时候，没有改变其值，也就是说这个值就是缺失的值，把所有的这样的值都添加到数组中，就得到了结果。

class Solution:
    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
        #原数组操作，先遍历一遍数组，令其值-1为索引的 所在数组中的元素+len(nums)
        #然后，再次遍历，把数组中的值小于len(nums)的下标+1，添加到res中
        if not nums:
            return []
        n = len(nums)
        res = []
        for i in range(n):
            index = (nums[i] - 1) % n 
            nums[index] += n 
        for i in range(n):
            if  nums[i] <= n:
                res.append(i+1)
        return res

思路2：

原数组操作，先遍历一遍数组，令其值的绝对值-1为索引的 所在数组中的元素为其自身绝对值的相反数，也就是置为负数；
然后，再次遍历，把数组中的值大于0的下标+1，添加到res中

class Solution:
    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
        # 原数组操作，先遍历一遍数组，令其值的绝对值 - 1为索引的所在数组中的元素为其自身绝对值的相反数，也就是置为负数；
        # 然后，再次遍历，把数组中的值大于0的下标+1，添加到res中
        if not nums:
            return []
        n = len(nums)
        for num in nums:
            index = abs(num) - 1
            nums[index] = -abs(nums[index])
        res = []
        for i in range(n):
            if nums[i] > 0:
                res.append(i + 1)
        return res

思路3：

遍历数组，把nums[i] 和i + 1对应起来，实现就是交换，直到nums[i] == nums[nums[i] - 1]：
	while nums[i] != nums[nums[i] - 1]:
   	 	nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]
再次遍历，找缺失的数字

代码如下：

class Solution:
    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
        #抽屉原理
        #构建原地哈希表
        for i in range(len(nums)):
            while nums[i] != nums[nums[i] - 1]:
                nums[nums[i] - 1],nums[i] = nums[i],nums[nums[i] - 1]
        #找缺失的数字
        res = []
        for i in range(len(nums)):
            if nums[i] != i + 1:
                res.append(i + 1)
        return res

当然，我们在交换的时候有个小窍门：

代码就不附上了，实现应该很容易。

3、复杂度分析：

方法1：
时间复杂度：O(N)
空间复杂度：O(N)
方法2：
时间复杂度：O(N)
空间复杂度：O(1)