Pythonアルゴリズム

PythonでTwo Sum問題を解く

このレッスンでは、合計が指定した値になる2つの要素を、リストを1回たどるだけで見つけるTwo Sum問題を解きます。

  • 中級
  • 約2分で読めます
  • 実行できるサンプル 1 件

はじめに

どんな問題を解決するか

価格の一覧と予算が与えられたとき、ちょうど予算になる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) の時間で解けます。

重要なポイント

  1. complement = target - value はペアを完成させる値です。
  2. seen はすでに訪れた各値をその位置に対応させるので、検索が速いです。
  3. if complement in seen: は前にあった値から相手を見つけます。
  4. seen[value] = index は確認のあとで保存するので、値が自分自身とペアになることはありません。
  5. 目標9では、値7が位置0にある相手2を見つけ、[0, 1] になります。

どんな場面で使う?

  • 決まった和や差になるペアを見つける。
  • ハッシュテーブルでメモリと速さを交換することを学ぶ。
  • とてもよく出る面接問題で、3-Sum などの土台です。

使わなくてよいとき

  • 並べ替え済みでメモリが限られる入力:両端からの2つのポインターなら余分なメモリを使いません。
  • 1つではなくすべてのペアが必要な場合:最初の一致で返さず、結果を集めます。

サンプルコード

コードを実行 →
main.py
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. 空のリスト、要素が1つだけのリスト、重複した値を含むリストで試す。
  2. 各ステップの後の状態を表示して、アルゴリズムの動きを観察する。
  3. 要素が100個、1,000個、10,000個のときの実行時間を測り、別の解き方と比べる。
Pythonコンパイラで実行 →

よくある間違い

確認の前に保存する

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 のレビューも受けられます。

すべてのチャレンジ