JavaScriptで合計がターゲット値と一致する配列内の3つの要素を見つける方法

本記事では、数値の配列とターゲットとなる合計値を受け取る関数 threeSum() の実装方法を解説します。この関数は、配列内に合計がターゲット値と一致する3つの数字が存在するかどうかを判定し、存在する場合はそのインデックスを配列で返し、存在しない場合は -1 を返します。

解決策のアプローチ

まず、補助関数 twoSum() を作成します。これは配列とターゲットの合計を受け取り、線形時間 O(N)・線形空間で、合計がターゲットに一致する2つの数字のインデックスを返す関数です。見つからない場合には -1 を返します。

次に、本体となる threeSum() 関数を実装します。この関数は配列内の各要素を順番に走査しながら、「ターゲットの合計から現在の要素を引いた値」に対して twoSum() を呼び出します。これにより、残りの2つの要素が見つかれば、3つすべてのインデックスが確定します。

この手法を用いれば、O(N²) の計算量で3つの要素を効率的に見つけることができます。それでは、実際のコードを見てみましょう。

コード例

const arr = [1,2,3,4,5,6,7,8];
const twoSum = (arr, sum) => {
    const map = {};
    for(let i = 0; i < arr.length; i++){
        if(map[sum-arr[i]]){
            return [map[sum-arr[i]], i];
        };
        map[arr[i]] = i;
    };
    return -1;
};
const threeSum = (arr, sum) => {
    for(let i = 0; i < arr.length; i++){
        const indices = twoSum(arr, sum-arr[i]);
        if(indices !== -1 && !indices.includes(i)){
            return [i, ...indices];
        };
    };
    return -1;
};
console.log(threeSum(arr, 9));
console.log(threeSum(arr, 8));
console.log(threeSum(arr, 13));
console.log(threeSum(arr, 23));

出力結果

コンソールには次のように出力されます。

[ 0, 2, 4 ]
[ 0, 2, 3 ]
[ 0, 4, 6 ]
-1

コードの解説

twoSum() では、オブジェクト map をハッシュマップとして活用しています。各要素について「sum - arr[i]」がすでにマップに登録済みかどうかを確認し、登録されていれば対応するインデックスと現在のインデックスを即座に返します。これにより、二重ループを使わず線形時間での探索が可能になります。

threeSum() では、各要素 i に対して twoSum(arr, sum - arr[i]) を呼び出します。戻り値が -1 ではなく、かつ取得したインデックスに i 自身が含まれていないことを確認したうえで、[i, ...indices] を返しています。同じ要素を重複して使わないためのチェックが重要なポイントです。

最後の呼び出し例 threeSum(arr, 23) のように、条件を満たす組み合わせが存在しない場合は -1 が返されることも確認できます。