JavaScriptで線形時間O(n)で解く「Two Sum(2つの合計)」問題

問題の概要

最初の引数に数値の配列、2番目の引数に目標の合計値(target)を受け取るJavaScript関数を作成します。

関数は、配列の中から2つの数値(連続していなくても構いません)を選び、その合計が目標値と一致する組み合わせが存在すれば、該当する2つの要素のインデックスを返します。

重要な条件は、この処理を線形時間 O(n)、つまり1回のループ走査で完了させることです。単純な二重ループによる総当たり(O(n²))ではこの条件を満たせないため、より効率的なアプローチが必要になります。

解法のポイント:Mapを使う理由

鍵となるのはMap(ハッシュマップ)の活用です。配列を先頭から1回だけ走査しながら、現在の数値とペアになる数(目標値から現在の数値を引いた値)をキーとしてMapに登録していきます。そして走査中に、すでにMapへ登録済みの数値と一致する要素に出会った時点で、そのインデックスのペアを即座に返します。

この方法なら各要素は最大1回しか参照されないため、全体の時間計算量はO(n)に抑えられます。

コード例

const arr = [1, 3, 5, 7, 9, 11];
const target = 16;

const twoSum = function(arr, target) {
    const map = new Map();
    for(let i = 0; i < arr.length; i++) {
        const num = arr[i];
        if(map.get(num) === undefined){
            // ペアになる数(補数)と自分のインデックスを登録
            map.set(target - num, i);
        }else{
            // 登録済みの補数が見つかったら答えを返す
            return [map.get(num), i];
        };
    };
};

console.log(twoSum(arr, target));

出力結果

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

[3, 4]

処理の流れを詳しく見る

target = 16 の場合、各ステップでの動作は以下の通りです。

• i = 0(num = 1):Mapに「15 → インデックス0」を登録
• i = 1(num = 3):Mapに「13 → インデックス1」を登録
• i = 2(num = 5):Mapに「11 → インデックス2」を登録
• i = 3(num = 7):Mapに「9 → インデックス3」を登録
• i = 4(num = 9):9 はすでにMapに登録済み(対応するインデックスは3)→ [3, 4] を返却

実際に 7 + 9 = 16 となり、目標値を満たす組み合わせが見つかるため、正しく [3, 4] が返されます。

計算量のまとめ

• 時間計算量:O(n) — 配列を1回走査するだけで完了します
• 空間計算量:O(n) — 最悪ケースでは全要素分のエントリをMapに保持します