two sum (hash で O(n))
相手を探すたびに、配列を歩き直している
和が target になる 2 つの位置を探す問題です。素直に書けば、1 つ目を決めて、その右側を全部見て相手を探し、見つからなければ 1 つ目をずらす。この形で何回比べることになるか、数だけ数えてみます。
JavaScript
let compares = 0;
for (let i = 0; i < nums.length; i++) {
for (let j = i + 1; j < nums.length; j++) compares += 1;
}
// 1000 個で 499500 回、10 万個なら約 50 億回原因ははっきりしています。i を 1 つ進めるたびに、右側をまた最初から見ているからです。
欲しいのは値そのものではなく「もう出たかどうか」
見方を変えます。今 nums[i] を見ているとき、組める相手はもう決まっています。target - nums[i] です。この値を右側から探しに行くのではなく、「左側にもう出ていたか」を聞くことにします。
聞く相手が配列なら、結局は端から歩くので何も変わりません。そこで、通り過ぎた値を控えておく場所を用意します。
JavaScript
const seen = new Map();
seen.set(7, 1); // 値 7 は 1 番目に出た、と控える
seen.has(7); // true — 控えが何件に増えても 1 回で返る配列の includes は中身が増えるほど遅くなりますが、Map の has は増えても変わりません。この差が、二重ループを 1 周に変えます。控える中身を「出たかどうか」ではなく「何番目に出たか」にしておくのは、返すのが値ではなく位置だからです。
控えるのは、探した後
順番を間違えると、静かに壊れます。nums = [3, 3] で target = 6 のときを追ってみてください。
先に自分を控えてから相手を探すと、i が 0 の時点で「3 はもう出ている」と自分自身を見つけます。返るのは同じ位置を 2 回使った答えで、これは誤りです。テストによっては形が合っているぶん、見つけるのに時間がかかります。
nums = [2, 7, 11, 15] で target = 9 を追うと、2 の番では欲しい値が 7 ですが控えはまだ空なので、2 を控えて次へ進みます。7 の番では欲しい値が 2 で、これはもう控えにあります。2 歩で終わりました。残りの 11 と 15 は一度も見ていません。
各歩で「まず探す、無ければ控える」の順に固定してください。こうすれば、控えに入っているのは必ず自分より左の要素だけになります。同じ値が何度も出てくる配列でも、控えが上書きされるだけで筋は通ります。
返すのは値ではなく位置
最後に仕様の確認です。返すのは [3, 7] のような値ではなく、[0, 1] のような位置です。しかも昇順に並べます。控えから出てくるほうが必ず左にいるので自然と昇順になりますが、組み立て方によっては入れ替わります。返す直前に並べておくと確実です。
答えは必ず 1 組あるという前提なので、見つからなかった場合を作り込む必要はありません。
要件
- 二重ループ
O(n^2)ではなくhashmapを使ったO(n)で解く - 戻り値は昇順にソートしたインデックスペア (例:
[0, 1]) - 同じインデックスを 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,5,8,3,4], 7) → [3,4]
twoSum([-1,-2,-3,-4,-5], -8) → [2,4]
twoSum([0,4,3,0], 0) → [0,3]ヒント
