题目

题目来源：力扣（LeetCode

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

思路分析

数学解法

高斯求和公式 求出 [0..n][0..n] 的和，减去数组中所有数的和，就得到了缺失的数字。高斯求和公式：
和 =（首项+末项）× 项数 / 2

  1. /**
  2.  * @param {number[]} nums
  3.  * @return {number}
  4.  */
  5. var missingNumber = function (nums) {
  6.   let n = nums.length;
  7.   // 利用高斯求和公式：和=（首项+末项）×项数/2  求出[0, n]中 n 个数的和
  8.   let dis = (1 + n) * n / 2;
  9.   // 减去数组中所有数的和，就得到了缺失的数字
  10.   for (let i = 0; i < n; i++) {
  11.     dis = dis - nums[i];
  12.   }
  13.   return dis;
  14. };

排序

  1. 首先对数组进行排序
  2. 然后在常数时间内判断两种特殊情况：
    • 0 没有出现在数组的首位，此时直接返回 0
    • n 没有出现在数组的末尾，此时直接返回 n

  3. 如果都不满足上述两种情况，那么缺失的数字一定在 0 和 n 之间，此时我们可以在线性时间内遍历排序后的数组，如果当前遍历的元素与当前的索引不相等，那么当前的索引就是缺失的数字。

    1. /**
    2. * @param {number[]} nums
    3. * @return {number}
    4. */
    5. var missingNumber = function (nums) {
    6. nums.sort((a, b) => a -b);
    8. // 判断 n 是否出现在末位
    9. if (nums[nums.length-1] != nums.length) {
    10.  return nums.length;
    11. }
    12. // 判断 0 是否出现在首位
    13. else if (nums[0] != 0) {
    14.  return 0;
    15. }
    17. // 遍历排序后的数组nums, 如果当前遍历的元素与当前的索引不相等，说明当前的索引就是缺失的数字
    18. for (let i = 0; i < nums.length; i++) {
    19.  if (nums[i] != i)  return i;
    20. }
    21. // 未缺失任何数字(保证函数有返回值)
    22. return nums.length;
    23. };

哈希表

将数组中的所有数字存到一个 Set 集合中，然后遍历 nums 数组，如果当前遍历的索引在 Set 集合中找不到，那么这个索引就是缺失的数字。

  1. /**
  2.  * @param {number[]} nums
  3.  * @return {number}
  4.  */
  5. var missingNumber = function (nums) {
  6.   const set = new Set();
  7.   // 将数组 nums 中的数字存储在 Set 集合中
  8.   for (let i = 0; i < nums.length; i++) {
  9.     set.add(nums[i])
  10.   }
  12.   // 遍历数组nums，如果 set 集合中不存在当前的索引数字，那么当前的索引就是缺失的数字
  13.   for (let i = 0; i < nums.length + 1; i++) {
  14.     if (!set.has(i)) return i
  15.   }
  17.   // 未缺失任何数字（保证函数有返回值）
  18.   return -1
  19. };