Skip to main content

缺失数字

题目​

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

进阶: 你能否实现线性时间复杂度, 仅使用额外常数空间的算法解决此问题?

提示:
  • n == nums.length
  • 1 <= n <= 10⁴
  • 0 <= nums[i] <= 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 中.

题解​

  1. 先用高斯求和公式: (首项 + 末项) * 项数 / 2, 求出从 0 到 n 的和应该是多少
  2. 减去给定的 nums 只和之后, 即缺失的数字.
/**
 * @param {number[]} nums
 * @return {number}
 */
var missingNumber = function (nums) {
  const n = nums.length
  const total = ((1 + n) * n) / 2

  return total - nums.reduce((acc, val) => acc + val)
}