二数の和 (map で O(n))
二数の和 (map で O(n))
このレッスンで分かること
- two sum は『見たことのある相手を高速に思い出す』問題
- 「整数配列
numsの中から 和がtargetになる 2 つの要素のインデックス を返せ」というのは、LeetCode No.1でもおなじみの two sum 問題 です- まず素朴に書くと、二重ループになります
二数の和 (map で O(n)) とは
配列の中から和が target となる 2 つの要素のインデックスを map を使って O(n) で見つける。
「整数配列 nums の中から 和が target になる 2 つの要素のインデックス を返せ」というのは、LeetCode No.1 でもおなじみの two sum 問題 です。一見、二重ループで O(n^2) が必要に見えますが、map (ハッシュマップ) を使うと O(n) で解けます。本レッスンは、map を使ったアルゴリズム最適化の 教科書例 です。
two sum は『見たことのある相手を高速に思い出す』問題。map を覚えるためにこれだけは絶対やる。
素朴な解法 (O(n^2))
まず素朴に書くと、二重ループになります。
Python
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
if nums[i] + nums[j] == target:
return [i, j]外側のループが n 回、内側のループも最悪 n 回なので、合計 O(n^2) です。n = 10000 なら 1 億回 の足し算と比較が走ります。これでは遅すぎるので、何とか O(n) にしたいところです。
map で 1 パス解法
発想を変えます。配列を 左から順に 走査するとき、現在見ている要素 v = nums[i] に対して、target - v (= 相方の値) がそれまでに既に見つかっていれば、その時点で解が確定します。「これまでに見た値とそのインデックス」を map に記録しておけば、相方の有無を O(1) で判定できます。
図のポイント (テキスト併記)
- 各要素は 1 度しか触らない ので、走査全体で
O(n)です
各要素は 1 度しか触らない ので、走査全体で O(n) です。map の get / set は平均 O(1) なので、追加コストは無視できます。
Python での実装
Python
def twoSum(nums, target):
seen = {}
for i, v in enumerate(nums):
need = target - v
if need in seen:
return [seen[need], i]
seen[v] = i
return [-1, -1]enumerate で index と value の両方を取り出します。need in seen が True なら、seen[need] (相方のインデックス) と i (現在のインデックス) のペアを返します。seen[v] = i を if の 後 に書く のがポイントです。先に書いてしまうと、target = 2 * v のケースで自分自身を相方にしてしまいます。
JavaScript での実装
JavaScript
function twoSum(nums, target) {
const seen = new Map();
for (let i = 0; i < nums.length; i++) {
const need = target - nums[i];
if (seen.has(need)) {
return [seen.get(need), i];
}
seen.set(nums[i], i);
}
return [-1, -1];
}ロジックは Python と完全に同じです。Map.has(key) が JavaScript の key in dict に相当します。
map のキーは『値』、バリューは『そのインデックス』。逆向きにしてしまうと『相方の値を検索する』ことができない。
Java / Go での実装
Java
import java.util.*;
public class Solution {
public static int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> seen = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int need = target - nums[i];
if (seen.containsKey(need)) {
return new int[]{ seen.get(need), i };
}
seen.put(nums[i], i);
}
return new int[]{ -1, -1 };
}
}Java は型に厳しいので、戻り値を int[] で組み立てるのを忘れずに。seen.containsKey(need) が Map.has に相当します。
計算量
配列の長さを n とすると、走査は n 回、map の get と set は平均 O(1)、よって全体は O(n)。空間計算量は最大 O(n) (map に最大 n 個のエントリ) です。O(n^2) から O(n) への落とし方の代表例として、本パターンは 多くの応用問題 に再利用できます。
配列を 1 周走査しながら map に履歴を残す、というアイデアは three sum、subarray sum k、longest substring without repeats などにも応用される。
よくある間違い
1 つ目は 同じインデックスを 2 度使う ケースです。nums = [3, 2, 4]、target = 6 で、nums[0] + nums[0] = 6 を解にしてしまう実装。seen[v] = i を if の 後 に書けばこの罠を避けられます。
2 つ目は map のキーを誤る ケース。「値 → インデックス」の向きが正しいです。逆にすると target - v の検索ができません。
3 つ目は 解が見つからないとき の戻り値です。本問では [-1, -1] を返す約束にしています。テストは「必ず解がある入力」のみ与えられる場合が多いですが、念のため落ちないようにしておきます。
やってみよう
nums = [2, 7, 11, 15]、target = 9を手で追って、[0, 1]が返ることを確認する。- 同じロジックで「和が target になるペアの個数」を返すバージョンを書いてみる。重複ありなしの議論も発生する。
- 配列がソート済みなら two pointer で
O(n)解法もある。両方書いて比較すると、map の汎用性と two pointer の省メモリ性のトレードオフが見えてくる。 - three sum (3 数の和が
target) は two sum を内側で呼ぶ典型応用。O(n^2)の見通しがつく。
よくある質問
Q. なぜ seen[v] = i を if の後に書くのですか？
A. if の前に書いてしまうと、target = 2 * v のケースで自分自身を相方として返してしまうためです。たとえば nums = [3, 5]、target = 6 のとき、v = 3 を先に seen に入れると need = 3 が既に seen に存在してしまい、同じインデックスを 2 度使う誤答を返します。先に「相方がいるか」を調べ、いなければ自分を記録する、という順序が正しい実装です。
Q. 解が必ず存在しない場合、戻り値はどう設計すべきですか？
A. 問題の制約によります。LeetCode No.1 の公式制約では「解は必ず 1 組だけ存在する」と保証されているため、ループを抜けることは想定されていません。ただし実務では制約が緩い場合もあるため、本レッスンのように [-1, -1] などの番兵値を返しておくか、例外を投げるか、あるいは None / null を返す設計にしておくと安全です。
Q. 同じ値が複数あるとき、どのインデックスが返りますか？
A. 最初にペアが成立した時点のインデックスが返ります。たとえば nums = [1, 4, 4, 9]、target = 8 のとき、i = 2（2 番目の 4）を見た瞬間に need = 4 が seen に存在し（i = 1 として記録済み）、[1, 2] が返ります。配列を左から 1 パスで走査するため、より左側のインデックスペアが優先されます。
Q. ハッシュマップの get / set は本当に O(1) ですか？
A. 平均計算量は O(1) です。ハッシュ関数でキーをバケット番号に変換し、そのバケットを直接参照するため、配列全体を探索しなくて済みます。ただし、ハッシュ衝突が多発する最悪ケースでは O(n) になりえます。実用上は言語標準のハッシュマップが衝突を分散させる工夫（チェイン法やオープンアドレス法）を持っているため、ランダムなデータでは O(1) と見なして問題ありません。
次のレッスン
次は アナグラム判定 に進みましょう。
事前確認 — 進む前に次の 3 つができることを確認しましょう。
- 二数の和 の要点を自分の言葉で説明できる
- このレッスンの最小コード (または操作手順) を見ずに書ける
- 練習問題やクイズで間違えた箇所を読み直して理解した
理解度チェック (30 秒)
Q. 二数の和 とは何か、1 文で説明してください。
A. 本文の「このレッスンで分かること」または冒頭の説明文を見直し、自分の言葉で要約できれば OK。詰まったら本レッスンの最初の H2 セクションを読み返してみましょう。
関連レッスン
要件
- 戻り値は [i, j] の 2 要素配列で、i < j を満たすこと
- map / HashMap / dict を使い、1 パスの O(n) で解く
- 同じインデックスを 2 度使ってはいけない (i != j)
入出力例
test-cases.txt
twoSum([2,7,11,15], 9) → [0,1]
twoSum([3,2,4], 6) → [1,2]
twoSum([3,3], 6) → [0,1]
twoSum([-1,-2,-3,-4], -7) → [2,3]
twoSum([1,5,3,8,2], 10) → [3,4]
twoSum([0,4,3,0], 0) → [0,3]