二数の和 (map で O(n))

100件で4950組、1万件で約5000万組

配列から、足して目標になる2つの値を見つけたいとします。金額の一覧で、合計が予算と一致する2件を探す場面です。まず思いつくのは、異なる位置の組をすべて試す方法です。同じ1件を2回使うことはできません。

n件から異なる2件を選ぶ組数は n × (n − 1) ÷ 2 です。100件なら4950組、1万件なら49995000組。全組を比べる処理は O(n²) です。件数が増えると、答えがあるかどうかを確かめるだけでも比較が増えます。

相方は、引き算で分かる

目標が10、いま見ている値が3なら、必要な相方は7です。目標から現在の値を引けば、探す値を1つに絞れます。

target = 10
v = 3
print(target - v)   # 7

あとは、相方が既に出てきたかを調べればよいのです。配列を毎回先頭から探すと、ここでも件数に比例する時間がかかります。

見た値と位置を控える

位置は先頭を0として数えます。辞書に値と位置を記録しておけば、見つかったときにどの2件かも答えられます。

seen = {}
seen[3] = 0
seen[7] = 1
print(7 in seen)   # True
print(seen[7])     # 1

in はキーがあるかを確かめ、角括弧は対応する位置を取り出します。各値について、相方を計算し、控えを確認し、なければ現在の値と位置を記録します。相方が見つかった時点で探索を止めます。

辞書の操作が平均 O(1) なら、n件を1回ずつ見る処理は平均 O(n) です。その代わり、相方が見つからない場合は最大n件ぶんの控えを持ちます。比較を減らすために記憶領域を使っています。

確認してから記録する

目標が現在の値の2倍の場合、記録を先にすると自分自身が相方として見つかります。確認を先にすれば、控えには必ず以前の位置だけがあり、同じ1件を2回使いません。同じ値が別の位置にあるなら、その2件は使えます。

例題で確かめる

配列 [4, 1, 6] から、目標8になる2件を探します。

答えは見つかりません。4は1件だけなので 4 + 4 は使えず、ほかの組も 4 + 1 = 5、4 + 6 = 10、1 + 6 = 7 で、目標8になりません。