Zenn
2️⃣

JavaScriptで解くLeetCode：Two Sum

2024/12/25に公開
JavaScript
LeetCode
tech

このシリーズでは、プログラミング学習サイトLeetCodeで一般公開されている問題の中から良問を厳選し、JavaScriptを用いてアルゴリズムを解説していきます。

この記事では、Arai60に収録されている「Two Sum」を解説します。

以下のサイトから問題に挑戦できます。
https://leetcode.com/problems/two-sum/description/

問題の概要

整数からなる配列 nums とある整数 target が与えられる。
このとき、足し合わせると target になる 2つの数のインデックスを返せ。

  • 同じ要素を2回使うことはできない
  • 必ず一つの解が存在するとする

例

Input: nums = [2, 7, 11, 15], target = 9
Output: [0, 1]
Explanation: nums[0] + nums[1] = 9 なので [0,1] を返す

制約

  • 配列の長さは 2 以上 10^3 以下
  • 配列要素および target は -10^9 以上 10^9 以下
  • 解は 必ず一つ存在すると仮定

非効率なアルゴリズム：二重ループ (O(n^2))

最初のアプローチとして、全てのペアを総当たりで調べる二重ループが考えられます。

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 [];
}
  • 時間計算量: O(n^2)
    配列が大きくなるにつれて処理時間が急増するため、パフォーマンス面で課題が残ります。

本題：Map を用いた効率的な実装 (O(n))

二重ループのボトルネックを解消するために、JavaScript の Map を利用する方法が非常に有効です。
ここでは、補完値（ターゲットを満たすために必要なもう1つの数値）という考え方を取り入れ、アルゴリズムをシンプルにまとめていきます。

1. Map で要素を管理するメリット

JavaScript の Map は以下のような操作を平均 O(1) の時間で提供してくれます：

  1. キーが含まれているかチェック → map.has(key)
  2. 値の取得 → map.get(key)
  3. キーと値の登録 → map.set(key, value)

これらにより、配列を一度走査するだけで target を達成するペアを見つけられます。

2. 「補完値」の考え方

  • 現在見ている要素を nums[i] とすると、「ターゲット target に達するために必要なもう1つの値」 は

complement = target − nums[i]

で表せます。

  • complement がすでに Map に登録されている値 として存在するならば、nums[i] + complement = target となるわけです。

補完値は保存しなくていい？

  • Map に保存するのは「これまでに見た数値 (nums[i])」と「そのインデックス (i)」のみ。
  • complement はその都度計算し、map.has(complement) で存在を即座に確認できます。

3. 実装例

function twoSum(nums, target) {
  const map = new Map(); // JavaScriptのMapを初期化

  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i];

    // もし complement が既に記録されていれば、答えを返す
    if (map.has(complement)) {
      return [map.get(complement), i];
    }

    // 今見ている値（nums[i]）とそのインデックス（i）を登録
    map.set(nums[i], i);
  }

  // 今回は必ず解がある前提だが、念のため。
  return [];
}

コードのポイント

  1. map.has(complement)
    • Map に complement というキーが存在するかを O(1) でチェック。
  2. map.get(complement)
    • 補完値のキーが存在していれば、インデックスをすぐ取り出せる。
  3. map.set(nums[i], i)
    • 「要素の値 → インデックス」で登録。常に最新のインデックスを保持します。

4. 計算量と空間量

  • 時間計算量: O(n)
    • 配列を一度走査し、各要素に対して Map の操作（検索・追加）を平均 O(1) で行います。
  • 空間計算量: O(n)
    • 最悪の場合、配列のすべての要素を Map に登録する可能性があります。

動作例

nums = [2, 7, 11, 15];
target = 9;
  1. i = 0, nums[0] = 2
    • complement = 9 - 2 = 7
    • map.has(7) → false
    • map.set(2, 0) // Map: { 2 => 0 }
  2. i = 1, nums[1] = 7
    • complement = 9 - 7 = 2
    • map.has(2) → true (インデックスは 0)
    • 答えとして [0, 1] を返す

まとめ

  1. 二重ループ (O(n^2)) でシンプルに総当たりする方法もあるが、配列が大きくなると処理時間がネックになる。
  2. Map を使った補完値のアイデア なら、要素を1回スキャンするだけで O(n) で問題を解決できる。
  3. Map には「見たことのある数値」と「そのインデックス」を保存し、必要に応じて complement = target - nums[i] をチェック すれば良い。
  4. 補完値そのものを保存する必要はなく、必要なときに計算すれば十分。

このアプローチは、ペアを探す問題やハッシュテーブル（連想配列）を活用する問題で非常に有用です。

次回以降も、Arai 60 の他の問題を JavaScript で解説していきますので、お楽しみに！

以上で、第1問「Two Sum」 の解説は終了です。

少しでもお役に立てれば幸いです。

ぜひ、同じアプローチでほかの問題も解いてみてください！

Discussion