JavaScriptで配列内の最初の重複要素のインデックスを検索する方法

今回は、配列の中で少なくとも2回出現する最初の要素のインデックスを返す関数を作成する方法を解説します。すべての要素が1回しか現れない場合は -1 を返す仕様とし、さらに定数空間(追加のメモリを使用しない)で処理を行うという条件も課します。

アプローチの考え方

この問題に対するシンプルかつ効果的な解決策は、for ループで配列を先頭から順に走査しながら、Array.prototype.lastIndexOf() メソッドを使って各要素の重複の有無をチェックする方法です。

具体的には、現在注目している要素 arr[i] について、lastIndexOf() が返すインデックスが現在のインデックス i と一致しない場合、その要素は配列内のより後ろの位置にも存在することになります。つまり、それが最初の重複要素であるため、その時点のインデックスを即座に返せばよいのです。

実装コード例

const arr1 = [0, 1, 1, 2, 3, 4, 4, 5];
const firstRedundant = arr => {
    for(let i = 0; i < arr.length; i++){
        if(arr.lastIndexOf(arr[i]) !== i){
            return i;
        };
    };
    return -1;
}
console.log(firstRedundant(arr1)); // 1

実行結果

上記のコードをコンソールで実行すると、次のような出力が得られます。

1

この例では、インデックス 1 の値 1 が、インデックス 2 にも存在するため、関数は 1 を返しています。

処理のポイントと注意点

• 追加メモリ不要: Set や Map などの補助データ構造を使わないため、定数空間という要件を満たしています。
• 時間計算量: lastIndexOf() は配列全体を走査するため、全体の計算量は O(n²) となります。パフォーマンスが重要な場合は、Set を使った O(n) の手法とのトレードオフを検討しましょう(ただしその場合は追加メモリが必要になります)。
• 早期リターン: 重複が見つかった時点ですぐに結果を返すため、無駄な走査を最小限に抑えられます。

このように、for ループと lastIndexOf() を組み合わせることで、追加メモリを使わずに配列内の最初の冗長(重複)要素のインデックスを効率的に特定できます。