Two Sum（LeetCode #1）
Two Sum は配列 nums から、和が target となる二つの添字を返します。一走査のハッシュ表解法は、各要素で「補数をすでに見たか」を問い、追加空間 O(n) と引き換えに、総当たり O(n²) を期待 O(n) 時間へ減らします。
来客一覧で、新人を登録する前に相手が来ているか調べる形です。検査してから書く順序が重要です。
Two Sum の仕組み
左から走査し、seen に値から添字への対応を保存します。位置 i で complement = target - nums[i] を計算します。補数があれば [seen[complement], i] を返し、前の添字を先にします。なければ seen[nums[i]] = i を書きます。
先に書くと nums[i] == target / 2 の時に自分と組めてしまいます。旧表を調べれば過去の添字だけが入り、異なる二位置を保証できます。
総当たりは二重ループで j > i の組を調べ、最大 n(n − 1)/2 組、追加空間 O(1) です。入力パネルで既定のハッシュ表と総当たりを同じ入力上で切り替えられます。
解法をステップで追う
既定は nums = [2, 7, 11, 15]、target = 18、ハッシュ表です。
i = 0、値 2：complement = 18 − 2 = 16。空表にないのでseen[2] = 0。i = 1、値 7：complement = 18 − 7 = 11。ないのでseen[7] = 1。表は{2: 0, 7: 1}。i = 2、値 11：complement = 18 − 11 = 7。添字 1 にあるので[1, 2]を返し、15 は訪ねない。
総当たりでは 2 + 7 = 9、2 + 11 = 13、2 + 15 = 17、7 + 11 = 18 の四検査で [1, 2] です。答えは同じですが、最悪の組数は二次的に増え、ハッシュ表は最大 n 要素の走査です。
画面右に配列、左に「値 | 添字」の表を置きます。要素の強調、補数計算、辞書検索、対の緑表示、または行の書き込み（追加、値が重複すれば上書き）の順です。総当たりでは辞書パネルが消え、追加記憶の差を示します。
時間・空間計算量
| 場合 | 総当たり | ハッシュ表 |
|---|---|---|
| 最良 | O(1)、最初の組 | O(1)、添字 0 と 1 |
| 末尾までの探索時間 | O(n²) | 期待 O(n) |
| 追加空間 | O(1) | O(n) |
ハッシュ表は一検索が期待 O(1) というモデルです。悪い衝突でも無条件に最悪 O(n) とは言えません。既定の n = 4 では表示段階の差は小さく、入力を増やすと二次列挙と線形走査の増え方が見えます。
境界ケース
入力画面は 3–8 個、値 1–99 に制限しています。それ以外は紙やコードで確かめられます。
- 解なし：原問題は一解を保証するが、表示する Python はループ末尾で
None。画面も解なしを示し、呼び出し側で扱う必要がある。 - 同値二つが解：
nums = [3, 3, 4]、target = 6では i = 1 が添字 0 の 3 を見つけ、[0, 1]。検査後の挿入で自己使用を防ぐ。 - 解以外の重複：後の同値は添字を上書きする。旧位置はその前に補数検査を済ませており、任意の合法解を探す上で安全。
- 負数と零：整数キーなので特別処理は不要。表示範囲外なだけ。
よくある間違い
- 挿入後に検査する。 半分の目標値を自分と組む恐れがあります。
- 添字ではなく値を返す。 辞書の値側に位置を保存します。
- ソートして元の添字を失う。 二ポインターでも解けますが、元位置を一緒に保持する必要があります。
- 集合だけを使う。 存在は分かっても、答えに必要な添字は得られません。