力扣第268题-丢失的数字

给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数。

示例 1：

输入：nums = [3,0,1]

输出：2

解释：n = 3，因为有 3 个数字，所以所有的数字都在范围 [0,3] 内。2 是丢失的数字，因为它没有出现在 nums 中。

示例 2：

输入：nums = [0,1]

输出：2

解释：n = 2，因为有 2 个数字，所以所有的数字都在范围 [0,2] 内。2 是丢失的数字，因为它没有出现在 nums 中。

示例 3：

输入：nums = [9,6,4,2,3,5,7,0,1]

输出：8

解释：n = 9，因为有 9 个数字，所以所有的数字都在范围 [0,9] 内。8 是丢失的数字，因为它没有出现在 nums 中。

提示：

n == nums.length
1 <= n <= 104
0 <= nums[i] <= n
nums 中的所有数字都 独一无二

2.1 方法一：辅助数组

构造一个全为哦，长度为len(nums)的辅助数组，然后遍历整个列表，将元素放到对应的下表下面，最后再遍历一遍辅助数组，看哪个索引的值是0，返回这个索引即可。

代码实现：

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        # 方法一 使用一个辅助数组
        n = len(nums)
        lst = [0] * (n + 1)
        for num in nums:
            lst[num] = 1
        for i in range(len(lst)):
            if lst[i] == 0:
                return i

2.2 方法二：哈希表

构造一个哈希表，键为nums数组的每一个值，value还是索引的每一个值(或者任意赋一个值即可)，最后从1~len(nums) + 1遍历吗，没有找到的那个key就是我们的结果。

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        # 方法二：哈希表
        hashmap = {}
        for num in nums:
            hashmap[num] = num
        for i in range(len(nums) + 1):
            if hashmap.get(i) is None:
                return i

2.3 方法三：使用in关键字(python)

这个也很简单，遍历从1 - len(nums) + 1的递增数列，依次判断每个值在不在列表中，如果不在那么直接返回这个值即可。

代码演示：

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        # 方法三: 使用python内置的in关键字
        for i in range(len(nums) + 1):
            if i not in nums:
                return i

这道题目相对来说比较简单，有很多种方法，还可以使用排序后再进行遍历的方法，只不过时间复杂度比上述三种时间复杂度高，感兴趣的可以去看力扣题解。