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

コンピューターサイエンス理論 / 全 5 枚

コンピューターサイエンス理論 - 二数の和 (map で O(n))

相方を探さずに引く

合計が target になる2つを探すとき、素直に二重ループを書くと全組み合わせを見ることになります。map に見た値を控えておけば、相方は探さずに引けます。

二重ループの O(n^2) が、1 回の走査 O(n) に変わります。効くのは map の検索が一発で終わるからです。

いま見ている値が決まれば相方の値も決まります。あとは、それを持っているかどうかだけの問題です。

const seen = new Map();
for (let i = 0; i < nums.length; i++) {
  const need = target - nums[i];
  if (seen.has(need)) return [seen.get(need), i];
  seen.set(nums[i], i);
}

1 / 5

← → キーでも送れます

このスライドが付いているレッスンを開く