JavaScriptで最初のn個の自然数列に含まれる重複要素を見つける2つの方法

1から始まる連続した自然数が格納された配列があるとします。ただし、そのうちの1つの要素が2回出現しているため、配列の長さは n+1 になっています。本記事では、この配列を受け取り、2回現れている数値を線形時間 O(n) で返す関数を、2つの異なるアプローチで作成していきます。

方法1：Array.prototype.reduce() を使う

やや技巧的ではありますが、記述するコード量が最も少ないのがこの方法です。まずはコードを見てみましょう。

const arr = [1,4,8,5,6,7,9,2,3,7];
const duplicate = a => a.reduce((acc, val, ind) => val+acc-(ind+1))+a.length-1;
console.log(duplicate(arr));

ここでは reduce() 関数を使用しています。コールバック関数は配列の各要素に対して1回ずつ実行され、今回の場合は次の3つの引数を受け取ります。

• acc … アキュムレータ（前回の処理で返された値）
• val … 現在処理中の要素の値
• ind … 現在処理中の要素のインデックス

それでは、次の配列にこのコードを適用して動きを確認してみます。

[ 2, 3, 1, 2]

この配列の長さは4ですが、initialValue 引数を渡していないため、イテレーションはインデックス1から開始され、アキュムレータにはインデックス0の値が初期値として代入されます。その結果、コールバック関数は合計3回実行されることになります。

1回目のパス

acc = 2, val = 3, ind = 1
戻り値 = 2+3 - (1+1) = 3

2回目のパス

acc = 3, val = 1, ind = 2
戻り値 = 3+1 - (2+1) = 1

3回目のパス

acc = 1, val = 2, ind = 3
戻り値 = 1+2 - (3+1) = -1

配列の終端に到達

走査が終わると reduce() の結果として -1 が返され、続けて次の計算が行われます。

-1 + (4-1) = -1 + 3 = 2

この値が duplicate() 関数から返されます。実際に重複していたのは「2」なので、正しい結果が得られていますね。

仕組みを整理すると、「各要素の値 −（インデックス＋1）」を順に加算していくと、最終的に「配列の総和 − 2〜n の総和」となります。そこに配列の長さ − 1 を足すことで、本来1〜(n−1)までしか存在しないはずの数列との差分、すなわち余分に1回出現した重複値だけが残るという理屈です。

方法2：Array.prototype.forEach() を使う

こちらの方法はより直感的です。配列を走査して総和を求め、そこから「最初の (n−1) 個の自然数の総和」（n は配列の長さ）を差し引きます。差し引いた後に残る値こそが2回出現した数値なので、それをそのまま返します。

コード例

const arr = [1,4,8,5,6,7,9,2,3,7];
const duplicate = a => {
    let sum = 0;
    const { length: n } = a;
    a.forEach(num => sum += num);
    return sum - ((n*(n-1))/2);
}
console.log(duplicate(arr));

出力

コンソールへの出力は次のようになります。

7

どちらの方法も計算量は O(n)、追加のメモリ消費はほぼゼロで済むため、大きな配列でも効率的に動作します。「短く書きたいなら reduce 版」「読みやすさを優先するなら forEach 版」というように、目的に応じて使い分けるとよいでしょう。