【Java】アルゴリズム徹底解説：配列内の要素の和が特定値になるインデックスを返す方法（Two Sum問題）

対象読者

• アルゴリズムの考え方を体系的に学びたい人
• データ構造（特に HashMap）の使い方を理解したい人
• Javaでアルゴリズム問題を実践的に学習したい人

問題

配列の中から2つの要素を選び、その和がtargetになるインデックスの組を返す関数を作成せよ。

---

問題の前提条件

• 配列 nums の要素は int 型とする。
• 2つの異なるインデックス i, j を選び、nums[i] + nums[j] == target となる組を探す。
• 該当するインデックスを配列 [i, j] の形で返す。

---

解き方パターン1：Brute Force（よくない例）

// 配列内の2つの要素の和がtargetになるインデックスを返す（非効率な例）
// pre: nums = [2,7,11,15], target = 9
// post: [0,1]（nums[0]+nums[1]=9）
public int[] twoSum(int[] nums, int target) {
    // 要素数が2未満ならペアを作れないので空配列を返す
    if (nums.length < 2) return new int[]{};

    // 結果を格納する配列を初期化
    int[] result = new int[2];

    // 二重ループで全てのペアをチェック
    for (int i = 0; i < nums.length; i++) {
        for (int j = i + 1; j < nums.length; j++) {
            // 2つの要素の和がtargetと一致すればそのインデックスを返す
            if (nums[i] + nums[j] == target) {
                result[0] = i;
                result[1] = j;
                return result;
            }
        }
    }

    // 該当するペアが存在しない場合は空配列を返す
    return new int[]{};
}

---

何がいけないのか

この実装では、外側と内側のループの両方で全要素を走査しているため、
計算量は O(n²) となります。

つまり要素数が1000個なら、最大で100万回の比較を行うことになります。
このように「すべての組み合わせを比較する」処理は、
入力サイズが大きくなると急激に非効率になるため、基本的には避けたい処理の仕方です。

---

解き方パターン2：HashMapを使った最適化例

// 配列内の2つの要素の和がtargetになるインデックスを返す（最適化版）
// pre: nums = [2,7,11,15], target = 9
// post: [0,1]（nums[0]+nums[1]=9）
class Solution {
    public int[] twoSum(int[] nums, int target) {
        // 各要素の値をキー、インデックスをバリューとして保持するハッシュマップを作成
        HashMap<Integer, Integer> map = new HashMap<>();

        // 結果格納用
        int[] result = {0, 0};

        // 配列を左から右へ1回のリニアスキャンで処理
        int index = 0;
        for (int num : nums) {
            // 「target - num」がすでにマップに登録されていればペア成立
            int complement = target - num;
            if (map.containsKey(complement)) {
                result[0] = map.get(complement);
                result[1] = index;
                break;
            }

            // まだ登録されていない場合は現在の要素をマップに追加
            map.put(num, index);
            index++;
        }

        return result;
    }
}

---

このコードの良い点

• リニアスキャン（O(n))
  配列を左から右へ1回だけ走査するだけで完結する。

• HashMapを活用して探索を高速化
  target - num が存在するかどうかの確認を O(1) で実行している

• ネストループを排除
  不要な組み合わせチェックがなくなり、処理効率が大幅に向上している。

---

ロジックの流れ

1. 空のHashMapを作成

   • キー：配列要素
   • 値：その要素のインデックス

2. リニアスキャンを開始

   • 各要素 num について target - num を計算。
   • その値がすでにHashMapのキーに存在すれば答えが見つかる。
   • なければ現在の num をキー、counter(インデックスとして)をバリューとしてマップに登録。

3. 結果を返す

   • 対応するインデックスのペア [i, j] を返す。

---

まとめ

• Brute Forceでは O(n²)、HashMapを使えば O(n) で処理可能。
• 1回のリニアスキャンと定数時間アクセスを組み合わせることで効率的に解ける。
• 「探索はHashMapで O(1) にする」考え方は、さまざまなアルゴリズムに応用可能。

---

個人的に思うこと

やはり配列×リニアスキャン×ハッシュマップ利用で最適化された方法で解ける問題は非常に多いので、マスターしたいパターンの一つですね。