算法

Find Missing Number in Sequence

给出数组，包含范围 [0, n] 中的整数，各不重复，找到缺失的唯一数字。

求和公式

对于指定范围的序列，缺失值可以通过求和公式计算，给出范围内所有整数之和减去给出的数组之和即为缺失值。

求和公式：

\sum_{i=1}^{n} i = \frac{n(n+1)}{2}

代码

function findMissingNumber(numbers: number[]): number {
  const n = numbers.length;
  const expectedSum = (n * (n + 1)) / 2;

  let actualSum = 0;
  for (const num of numbers) {
    actualSum += num;
  }

  return expectedSum - actualSum;
}

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

拓展

若给出的范围不是 [0, n]，而是 [a, b]，则求和公式为：

\sum_{i=a}^{b} i = \frac{(b-a+1)(a+b)}{2}

在 GitHub 上编辑

上次更新于

Find Element in Rotated Array

在一个排序后再旋转的、元素唯一的数组中，用对数时间找到 target 的下标。

Maximum Product in Contiguous Array

寻找连续子数组最大乘积

目录