LeetCode: Two Sumをわかりやすく

1. 問題の概要

「Two Sum（ツーサム）」という問題は、次のような問題です：

与えられるもの: 数字が並んだリスト（配列）と、特定の数字（ターゲット）。
やること: リストの中から、合計してターゲットになる2つの数字を探し、その数字の場所（インデックス）を答える。

2. 具体的な例

例えば、リストが [2, 7, 11, 15] で、ターゲットが 9 の場合を考えます。このとき、リストの中の 2 と 7 を足すと 9 になるので、これが答えです。2 はリストの最初（インデックスは 0）、7 はその次（インデックスは 1）なので、答えは [0, 1] になります。

3. 解き方の説明

方法1: 全部試してみる（ブルートフォース）

リストの中から1つ目の数字を選びます。
次に、その数字以外の他の数字を全部足してみて、ターゲットになるか確認します。
これを全部の数字で試して、ターゲットになる組み合わせを見つけます。
例:

まず 2 を選んで、7, 11, 15 と足してみます。2 + 7 = 9 でターゲットに一致します。
なので答えは 2 と 7 です。
この方法だと、たくさんの組み合わせを試すので時間がかかります。

方法2: ハッシュマップを使って素早く見つける

ハッシュマップという特別なメモ帳のようなものを使います。
リストの数字を順番に見ていきながら、その数字を使ってターゲットになるもう1つの数字を探します。
例えば、2 を見つけたとき、「ターゲットの 9 になるにはあと 7 が必要だな」と考えます。
そして「もう 7 を見つけているかな？」とハッシュマップに書き留めてあるか確認します。
もし、すでに書いてあれば、2 と 7 のインデックスを答えます。
例:

最初に 2 を見て、ハッシュマップに「2 はインデックス 0」と書き留めます。
次に 7 を見たとき、「9になるにはあと2が必要だな」と考えて、ハッシュマップを確認します。そこには「2 はインデックス 0」と書いてあるので、答えは [0, 1] になります。

JavaScriptで「Two Sum」問題を解くための2つの方法、ブルートフォースとハッシュマップを使った最適化アプローチのコード例を示します。

ハッシュマップの説明

ハッシュマップは、キーと値のペアを効率的に保存し、検索できるデータ構造です。ここでは、JavaScriptのオブジェクトを使ってハッシュマップをどのように利用するかを説明します。

例：簡単なハッシュマップの使い方

// ハッシュマップの初期化
const hashMap = {};

// キーと値のペアを追加
hashMap["apple"] = "りんご";  // "apple"というキーに"りんご"という値を関連付ける
hashMap["banana"] = "バナナ"; // "banana"というキーに"バナナ"という値を関連付ける
hashMap["cherry"] = "さくらんぼ"; // "cherry"というキーに"さくらんぼ"という値を関連付ける

// キーを使って値を取得
console.log(hashMap["apple"]);  // 出力: りんご
console.log(hashMap["banana"]); // 出力: バナナ

// キーの存在を確認
if ("cherry" in hashMap) {
    console.log("cherry is in the hashMap"); // 出力: cherry is in the hashMap
}

// キーと値の削除
delete hashMap["banana"];
console.log(hashMap["banana"]); // 出力: undefined （"banana"のエントリが削除された）

ハッシュマップの特徴と利点

高速なデータアクセス:
ハッシュマップはキーを使ってデータに直接アクセスするため、データの検索や追加が非常に速いです。

ユニークなキー:
各キーは一意であるため、同じキーを使って複数の値を格納することはできません。

動的なサイズ:
必要に応じて新しいキーと値のペアを追加できるため、サイズが動的に変化します。

このように、ハッシュマップは大量のデータの中から素早く特定のデータを見つけたり、保存したりするのに非常に便利です。

Javascriptを使った解答例

1. ブルートフォースアプローチ

この方法では、すべてのペアをチェックして、合計がターゲットに等しいかどうかを確認します

function twoSum(nums, target) {
    for (let i = 0; i < nums.length; i++) {
        for (let j = i + 1; j < nums.length; j++) {
            if (nums[i] + nums[j] === target) {
                return [i, j];
            }
        }
    }
    return null; // これは通常発生しませんが、解がない場合のために
}

// 使用例
const nums = [2, 7, 11, 15];
const target = 9;
const result = twoSum(nums, target);
console.log(result); // [0, 1]

2. ハッシュマップを使った最適化アプローチ

この方法では、数値を見ながらハッシュマップに保存し、必要な相方が既にハッシュマップにあるかどうかをチェックします。

function twoSum(nums, target) {
    const previousMap = {}; // 数字とそのインデックスを保存するオブジェクト（ハッシュマップの役割）

    for (let i = 0; i < nums.length; i++) { // nums配列の全要素に対してループを実行
        const currentNum = nums[i]; // 現在のインデックスiの要素（数値）を取得
        const difference = target - currentNum; // ターゲットから現在の数値を引いた値（必要な相方の数値）

        // previousMapにdifference（必要な相方の数値）が既に存在するかチェック
        if (previousMap.hasOwnProperty(difference)) {
            // 存在する場合は、[相方のインデックス, 現在のインデックス]を返す
            return [previousMap[difference], i];
        }

        // previousMapに現在の数値をキー、そのインデックスを値として保存
        previousMap[currentNum] = i;
    }
    return null; // 解がない場合（通常は発生しないが、念のため）
}

// 使用例
const nums = [2, 7, 11, 15]; // 入力配列
const target = 9; // 目標の合計
const result = twoSum(nums, target); // twoSum関数を呼び出し、結果をresultに格納
console.log(result); // 結果をコンソールに表示 [0, 1]

各アプローチの説明

ブルートフォースアプローチ:
このアプローチでは、2重ループを使ってすべてのペアを調べ、合計がターゲットと等しいペアを見つけます。時間計算量はO(n^2)です。

ハッシュマップを使ったアプローチ:
このアプローチでは、配列を1度だけ走査します。ハッシュマップを使って、各数値のインデックスを記録しながら、ターゲットとの差を調べます。差が既にハッシュマップにある場合、そのインデックスを返します。この方法は時間計算量がO(n)で、非常に効率的です。

どちらの方法も、入力された配列とターゲットの値に基づいて正しいインデックスペアを見つけます。ただし、ハッシュマップを使った方法の方が計算量が少なく、より効率的です。

4. まとめ

この方法2のハッシュマップを使う方法だと、リストを1回だけ見るだけで答えを見つけられるので、とても速く解くことができます。