LeetCode 冥想：缺失的数字

从现在开始，我们要努力学习啦！今天我给大家带来《LeetCode 冥想：缺失的数字》，感兴趣的朋友请继续看下去吧！下文中的内容我们主要会涉及到等等知识点，如果在阅读本文过程中有遇到不清楚的地方，欢迎留言呀！我们一起讨论，一起学习！

题目描述：给定一个包含 0 到 n 范围内的 n 个不同数字的数组 nums，找出该范围内数组中唯一缺失的数字。

示例：

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

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

输入：nums = [9, 6, 4, 2, 3, 5, 7, 0, 1]
输出：8
解释：n = 9，因为有 9 个数字，所以所有数字都在范围 [0, 9] 内。8 是范围内缺失的数字，因为它没有出现在 nums 中。

说明：所有 nums 中的数字都是唯一的。

一种简单的解法是计算范围的总和，然后减去给定数组的总和。剩余的值就是缺失的数字。可以使用 reduce 方法来计算数组的总和：

function missingNumber(nums) {
  const n = nums.length;
  const expectedSum = (n * (n + 1)) / 2;
  const actualSum = nums.reduce((sum, num) => sum + num, 0);
  return expectedSum - actualSum;
}

该方法的时间和空间复杂度均为 O(n)。

为了提高效率，可以使用位运算（异或）。 xor 运算的特性是：相同数字异或结果为 0，任何数字与 0 异或结果为自身。

我们可以将数组中每个数字与其索引进行异或运算。由于所有数字都是唯一的，最终所有数字都会抵消，只剩下缺失的数字。为了处理缺失数字等于数组长度的情况，我们将结果初始化为数组长度：

function missingNumber(nums) {
  let result = nums.length;
  for (let i = 0; i < nums.length; i++) {
    result ^= nums[i] ^ i;
  }
  return result;
}

该方法的时间复杂度为 O(n)，空间复杂度为 O(1)。

时间和空间复杂度分析：

时间复杂度：O(n)，因为我们需要遍历数组一次。 空间复杂度：O(1)，因为我们只使用了常数个额外的变量。

接下来，我们将继续探讨系列中的下一个问题。祝您编码愉快！

今天关于《LeetCode 冥想：缺失的数字》的内容介绍就到此结束，如果有什么疑问或者建议，可以在golang学习网公众号下多多回复交流；文中若有不正之处，也希望回复留言以告知！