PythonのTwo Sumアルゴリズム
ハッシュテーブルにより二重ループを避けられます。
PythonのTwo Sumアルゴリズムとは？
ハッシュテーブルにより二重ループを避けられます。
合計がtargetになる2つの値を探します。
どのような場面で使う？
- アルゴリズムとデータ構造を理解する。
- 各ステップと境界ケースを確認する。
- 実行時間とメモリ使用量を比較する。
サンプルコード
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]仕組み
補数をO(1)で検索するため、全体の時間O(n)、メモリO(n)です。
値を変更し、PythonをインストールせずにCodeUtilityオンラインPythonコンパイラで実行できます。
練習問題
入力値と境界ケースを変更し、より大きなデータでも動作を確認してください。
- 空入力、1要素、重複値を試す。
- 各ステップの状態を表示する。
- 別の解法と性能を比較する。