PythonでTwo Sum問題を解く
このレッスンでは、合計が指定した値になる2つの要素を、リストを1回たどるだけで見つけるTwo Sum問題を解きます。
はじめに
どんな問題を解決するか
価格の一覧と予算が与えられたとき、ちょうど予算になる2つの品物はどれでしょう。すべてのペアを調べれば分かりますが、およそ n² / 2 回の比較が必要です。すでに見たものを覚えておけば、1回通るだけで解けます。
身近なたとえ
Two Sum は、ちょうどの予算で買い物をするようなものです。値札を1つ見るたびに、あといくら足りないかを計算して、メモを確認します。ちょうどその値段の品物を、もう見かけたかな?見かけていれば、組み合わせが見つかりました。まだなら、この値段と見かけた場所をメモして、次へ進みます。
complement = target - value🤔 あと足りない値段if complement in seen:📋 その値段はもうメモにある?return [seen[complement], index]🛍️ 組み合わせが見つかった: 2つの位置seen[value] = index✍️ この値段と位置をメモして、先へ進むTwo Sum 問題は、合計が目標値になる2つの数のリスト内の位置を求めます。見た値を記録する辞書を使えば1回で、O(n) の時間で解けます。
重要なポイント
complement = target - valueはペアを完成させる値です。seenはすでに訪れた各値をその位置に対応させるので、検索が速いです。if complement in seen:は前にあった値から相手を見つけます。seen[value] = indexは確認のあとで保存するので、値が自分自身とペアになることはありません。- 目標9では、値7が位置0にある相手2を見つけ、
[0, 1]になります。
どんな場面で使う?
- 決まった和や差になるペアを見つける。
- ハッシュテーブルでメモリと速さを交換することを学ぶ。
- とてもよく出る面接問題で、3-Sum などの土台です。
使わなくてよいとき
- 並べ替え済みでメモリが限られる入力:両端からの2つのポインターなら余分なメモリを使いません。
- 1つではなくすべてのペアが必要な場合:最初の一致で返さず、結果を集めます。
サンプルコード
def two_sum(values, target):
seen = {}
for index, value in enumerate(values):
complement = target - value
if complement in seen:
return [seen[complement], index]
seen[value] = index
return []
print(two_sum([2, 7, 11, 15], 9))
実行結果
[0, 1]
コードの解説
辞書seenには、それまでにたどった値とその位置を保存します。各要素について、補数complement = target - valueを計算し、それがすでにseenにあるかを確認します。辞書の検索はO(1)なので、アルゴリズム全体はO(n)で動き、O(n)の追加メモリを使います。
値を変更し、PythonをインストールせずにCodeUtilityオンラインPythonコンパイラで実行できます。
発展問題
下のヒントにしたがってコードを書き換えてみましょう。自分で変えて結果を確かめると、コードを読むだけよりずっと深く理解できます。
- 空のリスト、要素が1つだけのリスト、重複した値を含むリストで試す。
- 各ステップの後の状態を表示して、アルゴリズムの動きを観察する。
- 要素が100個、1,000個、10,000個のときの実行時間を測り、別の解き方と比べる。
よくある間違い
確認の前に保存する
3が1つしかないのに 3 + 3 = 6 のように、値が自分自身とペアになることがあります。
seen[value] = index
if target - value in seen:
if target - value in seen:
return [seen[target - value], index]
seen[value] = index
このレッスンを終えましたか?
学習済みにすると進み具合を記録できます。
チャレンジで練習する
このレッスンの内容を使って実際の問題を解きましょう。各チャレンジはブラウザで動き、すぐにテストされ、AI のレビューも受けられます。
すべてのチャレンジ