二数の和 (map で O(n))
100 件で 4950 回、1 万件で 5000 万回
配列の中から、足して目標の数になる 2 つを見つけたい。まず思いつくのは総当たりです。1 番目と 2 番目、1 番目と 3 番目、と全部の組み合わせを試します。
組み合わせの数は、はっきり数えられます。
Python
n = 100
print(n * (n - 1) // 2) # 4950
n = 10000
print(n * (n - 1) // 2) # 49995000100 件なら 4950 回の足し算と比較で、これは一瞬です。1 万件になると約 5000 万回で、目に見えて待たされます。10 万件なら 50 億回で、もう終わりません。件数が 10 倍になるたび、比較は 100 倍。入れ子のループを書いた時点で、この増え方が確定します。
相方の値は、引き算だけで分かっている
総当たりが無駄なのは、探す相手が分かっているのに、総当たりしている ところです。
目標が 10 で、いま見ている値が 3 なら、必要な相方は 7 以外にありえません。
Python
target = 10
v = 3
print(target - v) # 7つまり本当に知りたいのは「この配列のどこかに 7 があるか」だけです。問題が「全部の組み合わせを試す」から「ある値が既に出てきたか」に置き換わりました。ここが分かれ目です。
見た値を控えておけば、探さなくて済む
「既に出てきたか」を配列に聞くと、また先頭からなめることになります。前回使った、値を渡せば一定時間で答えが返る入れ物を使います。
置くものが少しだけ違います。今回はキーを 見た値、中身を その値があった位置 にします。位置まで覚えておかないと、見つかったときに何番目だったかを答えられないからです。
Python
seen = {}
seen[3] = 0 # 値 3 は 0 番目にあった
seen[7] = 1
print(7 in seen) # True
print(seen[7]) # 1これで、配列を 1 周するあいだに答えが出ます。1 件あたりにやることは、引き算が 1 回、控えの確認が 1 回、控えへの記録が 1 回。どれも一定の時間なので、全体で O(n) です。1 万件なら 5000 万回が 1 万回になります。
その代わり、控えのぶんだけメモリを使います。最悪で全件ぶんです。時間を買うために場所を払っている、という取引になっています。
なお、控えを確認するのと記録するのは、順番を間違えると同じ位置の要素を 2 回使ってしまいます。目標がちょうど手元の値の 2 倍になる場合に何が起きるか、紙の上で 1 度たどってみてください。
要件
- 戻り値は [i, j] の 2 要素配列で、i < j を満たすこと
- map / HashMap / dict を使い、1 パスの O(n) で解く
- 同じインデックスを 2 度使ってはいけない (i != j)
入出力例
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]ヒント
