Hello Algo 探索最適化の教科書実装：線形探索をハッシュ探索に置き換える two_sum 戦略を読み解く

本稿は、オープンソースのアルゴリズム入門書「Hello Algo」の日本語版ドキュメント replace_linear_by_hashing.md（探索章）が解説する「線形探索をハッシュ探索に置き換えて時間計算量を下げる」最適化戦略を、実際のリポジトリに収録された多言語ソースコードと併せて徹底解説する技術記事です。「2 数の和（two_sum）」問題を題材に、$O(n^2)$ の総当たり解法が $O(n)$ のハッシュ解法へ変わる過程を、図解・実コード・複雑度比較の 3 視点から学びます。読み終える頃には、アルゴリズム設計で頻出する「空間計算量と時間計算量のトレードオフ」を自分の手で実装・検証できるようになります。

問題設定：和が target になる 2 要素を探す

本章が取り組む問題は、次の通りです。

!!! question "整数配列と目標値" 整数配列 nums と目標要素 target が与えられたとき、配列内から和が target となる 2 つの要素を探索し、それらの配列インデックスを返してください。任意の 1 つの解を返せば十分です。

これは競技プログラミングや面接対策でも定番の「two_sum」問題です。Hello Algo の日本語版コードベースでは、全言語共通のテストケースとして nums = [2, 7, 11, 15]、target = 13 が採用されており、正解は 2 + 11 = 13 に対応するインデックス [0, 2] です（例：Python 版ドライバコード の冒頭）。以降、この例を追いながら 2 つの解法を比較します。

解法 1：線形探索 —— 時間を犠牲にして空間を節約

考え方：すべてのペアを二重ループで検査

まず思いつくのは、考えられるすべての組み合わせを直接走査する方法です。二重ループを回し、各ラウンドで 2 つの整数の和が target になるかどうかを判定し、一致したらそのインデックスを返します。

内側のループを j = i + 1 から開始しているのは、同一要素の重複利用と同一ペアの重複列挙を避けるためです。この解法は追加のメモリを一切使わないシンプルさが利点ですが、要素数が大きくなると急激に破綻します。

実装と計算量

Python 版の実装は two_sum.py の two_sum_brute_force() として収録されています。

def two_sum_brute_force(nums: list[int], target: int) -> list[int]:
    """方法 1：総当たり列挙"""
    # 2重ループのため、時間計算量は O(n^2)
    for i in range(len(nums) - 1):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]
    return []

計算量評価

• 時間計算量：$O(n^2)$ —— 外側ループと内側ループの組み合わせをすべて検査します。n 個の要素に対して約 n(n-1)/2 回の比較が発生します。
• 空間計算量：$O(1)$ —— インデックスを保持する定数分の変数しか使いません。

この方法は空間効率は最高ですが、大規模データでは非常に時間がかかるのが欠点です。同じ方針の実装は C++ 版 twoSumBruteForce() や Go 版 twoSumBruteForce() にも確認できます。

解法 2：ハッシュ探索 —— 空間を犠牲にして時間を節約

考え方：補助ハッシュテーブルで「相棒」を即座に探す

線形探索が遅い原因は「過去に登場した要素を、毎回ループで探し直す」ことにあります。そこで、ハッシュテーブル（連想配列）を補助データ構造として用意し、キーを配列要素、値を要素のインデックスとして記憶します。配列を単一ループで走査しながら、各ラウンドで次の 2 ステップを実行します。

1. 数値 target - nums[i]（= 現在の要素の「相棒」候補）がハッシュテーブル内に存在するかを判定します。存在すれば、その 2 つの要素のインデックスを直接返します。
2. まだ見つからない場合は、キーと値の組 nums[i] → i をハッシュテーブルに追加して先へ進みます。

ステップごとの動作を図で追う

例 nums = [2, 7, 11, 15]、target = 13 での動作を見てみましょう。

ステップ 1：i = 0、要素 2 を処理 target - 2 = 11 はハッシュテーブルに未登録のため、2 → 0 を登録して次の要素へ進みます。

ステップ 2：i = 1、要素 7 を処理 target - 7 = 6 はハッシュテーブルに未登録のため、7 → 1 を追加します。ここではまだ解は見つかりません。

ステップ 3：i = 2、要素 11 を処理 target - 11 = 2 をハッシュテーブルで検索すると、先ほど登録した 2（インデックス 0）が即座にヒットします。よって解はインデックス [0, 2] です。

この例からわかる通り、ハッシュテーブルを使えば「過去の要素の探索」が $O(1)$ の期待時間で完了するため、全体の走査は 1 周で済みます。

実装と計算量

Python 版の実装は同じく two_sum.py の two_sum_hash_table() です。

def two_sum_hash_table(nums: list[int], target: int) -> list[int]:
    """方法 2：補助ハッシュテーブル"""
    # 補助ハッシュテーブルを使用し、空間計算量は O(n)
    dic = {}
    # 単一ループで、時間計算量は O(n)
    for i in range(len(nums)):
        if target - nums[i] in dic:
            return [dic[target - nums[i]], i]
        dic[nums[i]] = i
    return []

実装上の重要な注意点：「先に判定、後に挿入」の順序 ハッシュテーブルへの追加は、判定に失敗した後に行われます。これは単なる実装上の好みではなく、同一要素の 2 回利用を防ぐための必須条件です。もし先に nums[i] を登録してから検索すると、2 * nums[i] == target となる要素（例：target = 4 のときの要素 2）で、自分自身との組み合わせ [i, i] を誤って解として返してしまいます。先に検索してから登録する順序を守ることで、このバグを構造的に回避しています。この順序は全言語の実装で統一されており、C++ 版 の twoSumHashTable() でも dic.find() → dic.emplace() の順、Go 版 でもマップ参照 → 代入の順で確認できます。

計算量評価

• 時間計算量：$O(n)$ —— 配列を 1 周するだけ。各回のハッシュ検索・挿入は平均 $O(1)$ です。
• 空間計算量：$O(n)$ —— 最大 n 個のキーと値の組を保持する補助ハッシュテーブルが必要です。

Hello Algo の本文では、この方法は時間と空間の効率のバランスが総合的により良く、本問の最適解であると結論付けています。リポジトリでは Java、C、C#、Dart、JavaScript、Kotlin、Ruby、Rust、Swift、TypeScript、Zig にも同一アルゴリズムが収録されており、言語横断で比較学習できます。

C 言語でのハッシュテーブル実装のポイント

なお、標準ライブラリにハッシュテーブルを持たない C 言語版では、two_sum.c においてオープンソースの uthash ライブラリを利用しています。HASH_FIND_INT による検索と HASH_ADD_INT による挿入を find() / insert() 関数としてラップし、インデックスを val として保持する構造になっています。

typedef struct {
    int key;
    int val;
    UT_hash_handle hh; // uthash.h を用いて実装
} HashTable;

このように、言語が変わっても「検索を $O(1)$ にする補助データ構造を用意する」という戦略そのものは変わりません。

2 つの解法の比較：トレードオフの全体像

両解法の違いを表にまとめます。

評価軸	解法 1：総当たり（線形探索）	解法 2：補助ハッシュテーブル
時間計算量	$O(n^2)$（二重ループ）	$O(n)$（単一ループ＋平均 $O(1)$ のハッシュ探索）
空間計算量	$O(1)$（追加メモリなし）	$O(n)$（補助ハッシュテーブル）
探索対象のデータ規模	小規模向け	大規模・実用的なデータ向け
実装の複雑さ	非常にシンプル	やや複雑（ハッシュテーブルの管理が必要）

解法 1 は「時間を犠牲にして空間を節約」、解法 2 は「空間を犠牲にして時間を節約」する典型例です。CPU とメモリのどちらに余裕があるかによって選択は変わり得ますが、現代の実行環境ではメモリコストに対して時間コストの方が支配的であることが多く、解法 2 が実務上は有利です。リポジトリ内のドライバコードでは両解法を同一入力で実行し、どちらも [0, 2] を返すことを確認できます（例：Python 版の実行例）。

本章から得られる汎用的な最適化戦略

本稿で扱った手法は、単なる「1 問の解法」ではなく、アルゴリズム設計における代表的な戦略パターンです。

• 「ループ内で毎回全体を線形探索している」箇所は、ハッシュテーブル（辞書・マップ）による $O(1)$ 参照へ置き換えられる。
• その代償として、要素とインデックス（または関連情報）を保持する補助構造の分だけ空間計算量が増える。
• この「時間↔空間のトレードオフ」は、検索アルゴリズム全体の性質を論じる searching_algorithm_revisited.md や、他の章で登場する各種最適化手法を理解する際の土台になります。

具体的には、ハッシュテーブルの仕組み（衝突処理・リサイズ）は ハッシュマップの章、文字列・オブジェクトの同一性判定や重複除去（順列・部分和問題など）でも、この「線形探索をハッシュ検索へ」という発想が繰り返し活用されます。今回の two_sum を通じて体得した「探索コストのボトルネックを補助データ構造で取り除く」思考法は、ほぼすべてのアルゴリズム問題で応用可能です。

まとめ

• 問題：nums から和が target になる 2 要素のインデックスを求める。
• 解法 1（総当たり）：二重ループで全ペアを検査。時間 $O(n^2)$、空間 $O(1)$。
• 解法 2（ハッシュ）：補助ハッシュテーブルに「要素 → インデックス」を登録しながら、target - nums[i] を毎回 $O(1)$ で検索。時間 $O(n)$、空間 $O(n)$。「先に検索、後に登録」の順序で同一要素の重複利用を防ぐ。
• 結論：両者のトレードオフを踏まえれば、ハッシュ解法が本問のバランスの良い最適解であり、その背後にある「線形探索をハッシュ探索へ置き換える」戦略は他問題にも広く応用できる。

対応する日本語版ソースコード一式（Python・C++・C・Go・Java ほか全 13 言語）は ja/codes/ 配下の各 chapter_searching/two_sum.* に格納されており、書籍のコードスニペット（原文ドキュメント）と照合しながらそのまま実行・検証できます。