ハッシュマップ 1 パス探索で O(n) を実現
💡 一言で言うと：「リストの中から 足すと target になる 2 つの数のインデックス を探す問題」
💡 この問題を一言で言うと
「整数リスト
nums
の中から、合計が
target になる
2
つの要素を見つけ、そのインデックス（位置番号）を返す問題」です。答えは必ず
1 組だけ存在することが保証されています。
⚠️ なぜ単純な「全探索」では不十分なのか
Example 1
nums = [2,7,11,15]
target = 9
→ [0, 1]
nums[0]+nums[1] = 2+7 = 9 ✅
Example 2
nums = [3,2,4]
target = 6
→ [1, 2]
nums[1]+nums[2] = 2+4 = 6 ✅
Example 3（重複値）
nums = [3,3]
target = 6
→ [0, 1]
同じ値でも異なるインデックス ✅
📌 制約
各ステップをクリックするか ▶ Play で自動再生できます。
📋 このコードの構造（先に全体像を把握しよう）
seen = {}
という空の辞書（メモ帳）を用意する
enumerate()
でインデックスと値を同時に取り出しながらループする
target - num）が
seen
にあれば答えを返す
seen
に記録して次へ
from __future__ import annotations
from typing import List
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
# {数値: そのインデックス} を記録する「メモ帳」を用意する。
# dict は CPython 内部でハッシュテーブルを使っており
# キー検索が O(1)（一定時間）で完了する。
# リストの `in` 演算（O(n)）より大幅に速い。
seen: dict[int, int] = {}
# enumerate() でインデックス i と値 num を同時に取得する。
# C 実装なので手書きの for+range より高速で可読性も高い。
for i, num in enumerate(nums):
# 「target から今の数を引いた値」= 補数（complement）。
# もし補数が seen にあれば、そのペアが答えになる。
complement: int = target - num
if complement in seen:
# seen[complement] → 補数のインデックス（過去に記録）
# i → 現在のインデックス
return [seen[complement], i]
# ペアが見つからなければ今の数を記録して次へ。
# 後のループで「この数が誰かの補数」として参照される。
seen[num] = i
# 問題の制約上ここには到達しないが pylance 警告抑制のため。
raise ValueError("No valid pair found.")▶ 入力例 nums=[2,7,11,15], target=9 での動作トレース
初期状態: seen = {}
i=0, num=2
complement = 9 - 2 = 7
7 in {} → No
seen = {2: 0}
i=1, num=7
complement = 9 - 7 = 2
2 in {2: 0} → Yes ✅
return [seen[2], 1] = [0, 1]
出力: [0, 1]
→ nums[0]=2 と nums[1]=7 の和が 9 になる
🗺️ フローチャートの読み方
🔎 入力例 nums=[2,7,11,15], target=9 でのフロー追跡
seen
を初期化x、添字を
i とする）need = target - x
を計算need
が辞書に存在するか確認 → 存在すれば即座に
[seen[need], i]
を返却seen[x] = i
を実行して現在の値を記録（同値があればインデックスを更新）ValueError
を送出（問題前提では到達しない）
📖 Big-O 記法の読み方（入力 n が増えると処理時間がどう変わるかの目安）
| アプローチ | 時間計算量 | 空間計算量 | 可読性 | 備考 |
|---|---|---|---|---|
| 二重ループ（全探索） | O(n²) | O(1) | ★★★ | Follow-up の制約を満たさない |
| ✅ ハッシュマップ 1 パス | O(n) | O(n) | ★★★ | 推奨 — 最速かつシンプル |
🔍 なぜ O(n) になるのか
nums を
1 度だけ先頭から末尾まで走査します（= O(n)）。
各イテレーションで行う「辞書の検索」と「辞書への記録」はどちらも
O(1) です。 したがって全体の時間計算量は O(n) × O(1) =
O(n) になります。 空間計算量は最悪ケース（答えが末尾 2
要素のとき）に n-1 個の数値を辞書に記録するため O(n) です。
このページで登場した専門用語を五十音順でまとめました。分からない言葉が出てきたときに参照してください。
0
から始まります。例：nums[0]
は先頭の要素。
for i, val in enumerate(nums):
のように使います。
def f(x: int) -> str:
のように書きます。pylance（VSCode
の型チェッカー）が実行前に型の不一致を検出できるようになります。
num
とペアになるべき数値。complement = target - num
で計算します。例：target=9, num=2 のとき補数=7。
dict
がこれにあたります。
dict・enumerate()
などの組み込み関数の多くがC実装のため高速です。本解説が対象とする環境です。