【JavaScript】Two Sum（二数の和）問題をO(n)で解く効率的なアルゴリズム

この記事では、Two Sum（二数の和）問題を線形時間 O(n) 以内で解く関数の実装方法を解説します。

Two Sum問題とは

整数の配列が与えられたとき、その中から合計すると特定のターゲット値になる2つの数を見つけ出すのがTwo Sum問題です。

twoSum 関数は、合計がターゲットと一致する2つの数のインデックスを配列で返します。条件を満たす組み合わせが存在しない場合は、空の配列を返します。

O(n)で解くためのアプローチ

全てのペアを総当たりで調べる方法では計算量が O(n²) になってしまいます。そこで、ハッシュマップ（オブジェクト）を活用します。

具体的には、これまで走査した要素を「値 → インデックス」の形式でマップに記録していきます。各要素を処理する際、「ターゲットから現在の要素を引いた値（相方となる数）」がすでにマップに存在するかを確認します。存在すればそのインデックスと現在のインデックスを返し、ループを最後まで回しても見つからなければ空の配列を返します。こうすることで、配列を一度だけ走査すればよく、全体の計算量は O(n) に抑えられます。

コード例

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

const twoSum = (arr, sum) => {
    const map = {};
    for(let i = 0; i < arr.length; i++){
        // ターゲットから現在の要素を引いた値を求める
        const el = sum - arr[i];
        // 相方の数がすでにマップに存在すれば答え
        if(map[el]){
            return [map[el], i];
        }
        // 現在の要素をマップに記録
        map[arr[i]] = i;
    }
    return [];
};

console.log(twoSum(arr, sum));
console.log(twoSum(arr, 12));
console.log(twoSum(arr, 13));
console.log(twoSum(arr, 14));
console.log(twoSum(arr, 24));

出力結果

コンソールには以下のように表示されます。

[ 2, 5 ]
[ 1, 2 ]
[ 1, 3 ]
[ 3, 6 ]
[]

このようにハッシュマップを使うことで、余分なネストしたループを排除しつつ、1回の走査でTwo Sum問題を効率よく解くことができます。