leetcode-two-sum

LeetCodeのTwo SumをJavaで解いてみた

今回は、LeetCodeの定番問題「Two Sum」をJavaで実装しながら、初心者にもわかりやすく解説します。
基本的な全探索から、計算量を改善したハッシュマップを使った最適解まで紹介します。

問題の概要：LeetCode Two Sumとは？

LeetCodeの問題文をこちらに記載しておきます。
問題の要約：
整数の配列 nums と、整数 target が与えられたとき、
その合計が target になるような2つの数のインデックスを返す問題です。

入力例：

nums = [2, 7, 11, 15]
target = 9
# 出力: [0, 1]（nums[0] + nums[1] = 9）

制約として、「必ず1つの解が存在する」と明記されています。

自分の最初の回答（素直な2重ループ）

最初は思いつくまま、2重ループで全探索してみました。

public int[] twoSum(int[] nums, int target) {
    for (int i = 0; i < nums.length; i++) {
        for (int j = i + 1; j < nums.length; j++) {   //jをi+1としているのは重複を防ぐため
            if (nums[i] + nums[j] == target) {
                return new int[]{i, j};
            }
        }
    }
    throw new IllegalArgumentException("No two sum solution");
}

結果： 正しく動作しますが、O(n^2) で非効率です。

より効率的な解法：HashMapを使う

次に、HashMapを使って計算量を O(n) に改善します。

import java.util.HashMap;

public int[] twoSum(int[] nums, int target) {
    HashMap<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int diff = target - nums[i];
        if (map.containsKey(diff)) {
            return new int[]{map.get(diff), i};
        }
        map.put(nums[i], i);
    }
}

解説

正直最初はなぜこれでできるのか理解できませんでしたが、理解できたらスッキリしたので解説します。

🌀 1周目（i = 0）

nums[i] = 2
target - nums[i] = 9 - 2 = 7
map はまだ空なので、7 は見つからない（map.containsKey(7) = false）
→ ここで初めて map に 2 を登録（map.put(2, 0)）

🌀 2周目（i = 1）

nums[i] = 7
target - nums[i] = 9 - 7 = 2
map に 2 が入っている！（1周目で登録した）
→ 答えが見つかる！ return [map.get(2), 1] → [0, 1]

つまりこのコードは、「今までに見た数字をmapに保存しておいて、次の数字がペアになるかを調べている」んです。

なぜ「先に map に入れない」のか？

もし map に入れる処理を if文より前に書いてしまうと、同じ数字を2回使ってしまうというバグの原因になります。

このように「今の数字を使う前に、過去にその相方がいたかどうかを先にチェック」するのが正しい流れです。

まとめ：ループ順とマップの役割が全て

mapには「過去に出てきた数字とインデックス（for文の中のi）」を保存している
「今の数字のペア（targetとの差）」がすでに出ていたら、ペア完成
だから map に入れるのは if の後！順番が超大事

最初は意味が分からなくても、1周目・2周目を紙に書いてみると、一気に納得できると思います。
Two Sumはアルゴリズム初学者にとって、マップの使い方を学ぶのに最高の題材ですね。

【Javaで解説】LeetCode Two Sumを解いてみた｜初心者向け解説