JavaScriptで数値配列から欠落している要素を効率的に見つける方法

本記事では、長さnの数値配列を受け取り、その中で欠落しているたった1つの整数を見つけるJavaScript関数を作成します。配列には本来0からnまでの整数がすべて含まれているはずですが、そのうち1つだけが欠けています。しかも、どの数字が欠けているのかは事前に分からず、配列もソートされていません。

問題のポイント

• 配列の長さはnで、0〜nまでの整数が1つだけ欠けた状態で格納されている
• 配列はソートされていない
• 線形時間（O(n)）かつ定数領域（O(1)）で解決する必要がある

解決のアプローチ：合計値の差を利用する

配列には0からnまでの数字が1つだけ欠けて含まれています。ここで「0からnまでの連続する整数の総和」は、有名なガウスの公式である n × (n + 1) / 2 を使えば定数時間で求められます。

そこで、以下の手順で欠落した数字を特定できます。

1. reduce() メソッドなどを使い、配列内の全要素の合計を線形時間で計算する
2. ガウスの公式で求めた「あるべき総和」から実際の合計を差し引く
3. その差こそが欠落している数字となる

なぜなら、あるべき総和と実際の総和との差異は、欠けている1つの数字によってのみ生じるからです。

実装コード例

const arr = [3, 7, 8, 10, 11, 0, 2, 6, 1, 4, 5];

const findMissing = (arr = []) => {
  // 配列内の全要素の合計を計算（線形時間）
  const sum = arr.reduce((acc, val) => acc + val);

  // ガウスの公式で0〜nの総和を求める（定数時間）
  const num = arr.length;
  const correctSum = (num * (num + 1)) / 2;

  // 差が欠落している数字
  return correctSum - sum;
};

console.log(findMissing(arr));

出力結果

上記のコードをコンソールで実行すると、欠落している数字が以下のように出力されます。

9

処理の流れを確認

サンプル配列の長さは11なので、本来は0〜11までの12個の整数が存在するはずです。0〜11の総和は 11 × 12 / 2 = 66 であり、一方で配列の実際の合計は57です。この差 66 − 57 = 9 が、まさに配列から欠けている数字となります。

まとめ

合計値の差を利用する方法なら、追加のデータ構造を一切必要とせず、1回の走査（O(n)）だけで欠落した数字を検出できます。シンプルながらメモリ効率にも優れた定番アルゴリズムなので、コーディング面接などでも役立つテクニックとして覚えておきましょう。