JavaScriptで合計してターゲット値になるすべてのペアを検索する方法

JavaScriptでは、数値の配列を第1引数として受け取り、目標となる合計値(target)を第2引数として受け取る関数を実装する必要があります。

この関数は、配列内から2つの数値を選んだときに、その合計が指定された目標値と一致するすべてのペアを抽出し、配列として返すものです。

アプローチ

ここではマップ(ハッシュ)オブジェクトを活用してペアを効率的に検出します。具体的には、配列を先頭から順に走査しながら、「目標値 − 現在の値」に相当する数値(相方となる数)をキーとして記録していきます。後から走査した要素がそのキーに一致すれば、合計が目標値になるペアが存在すると判断でき、結果配列に追加します。

この方法により、二重ループによる総当たり(O(n²))を避け、O(n)の時間計算量で問題を解くことができます。

コード例

const arr = [7, 0, -4, 5, 2, 3];
const allTwoSum = (arr, target) => {
    const map = {};
    const results = [];
    for (let i = 0; i < arr.length; i++) {
        if (map[arr[i]]) {
            results.push([target − arr[i], arr[i]]);
            continue;
        }
        map[target − arr[i]] = true;
    }
    return results;
};
console.log(allTwoSum(arr, 5));

実行結果

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

[ [ 0, 5 ], [ 2, 3 ] ]

この結果は、配列内で 0 + 5 = 5 および 2 + 3 = 5 という2組のペアが発見されたことを意味しています。マップを利用することで、各要素を一度だけ走査するだけで目的のペアをすべて見つけられる点が、このアルゴリズムの大きな利点です。