1. 题目

给定一个包含 [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 中。

示例 4：

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

2. 解一：排序法

思路： 先排序，再遍历一遍数组

javascript
function missingNumber(number) {
  number.sort((a,b) => a - b)
  const len = number.length
  for(let i = 0; i < len; i++) {
    if(number[i] !== i) {
      return i
    }
  }
  return len
}

复杂度分析

• 时间复杂度：O(nlongn)
• 空间复杂度：O(1)

3. 解二：哈希集合法

思路： 将数组中的每个元素加入哈希集合，然后依次检查从 00 到 nn 的每个整数是否在哈希集合中，不在哈希集合中的数字即为丢失的数字。

javascript
function missingNumber(number) {
  const set = new Set(number)
  const len = number.length
  for(let i = 0; i <= len; i++) {
    if(!set.has(i)) {
      return i
    }
  }
}

复杂度分析

• 时间复杂度：O(n)
• 空间复杂度：O(n)

4. 解三: 位运算法

思路：

0,1,2...len,number[0],number[1]...number[len-1]

在上面一系列数中，可以发现我们想要的数只出现一次，其余都出现了两次。 据出现的次数的奇偶性，使用按位异或运算得到丢失的数字。 根据

javascript
function missingNumber(number) {
  let n = 0
  const len = number.length
  for(let i = 0; i < len; i++ ) {
    n ^= number[i] ^= i
  }
  return n ^= len
}

复杂度分析

• 时间复杂度：O(n)
• 空间复杂度：O(n)

5. 解四：数学法

思路： 将从 0 到 len 的全部整数求和 再将 number[0] 到number[len-1] 的全部整数求和 差值就是我们要求的值

javascript
function missingNumber(number) {
  const len = number.length
  let num = len * (len + 1) / 2
  for(let i = 0;i < len; i++) {
    num -= number[i]
  }
  return num
}

复杂度分析

• 时间复杂度：O(n)
• 空间复杂度：O(1)