読者です 読者をやめる 読者になる 読者になる

配列における3つの要素の和

3Sum しゃくとり法

Problem

leetcode.com

与えられた配列において、任意の3点の和がゼロとなる組合せを全て取得する問題。

Solution

この問題は以下のように解くことができる。

  1. 任意の3点をstart, middle, endと置く(start < middle < end)
  2. startを固定し、middle = start + 1, end = arr.length - 1 と置く
  3. 上記により3点が決まるので、3点の和を計算しsと置く
  4. s == sumならば、その要素達をリストに追加。この時、middle++, end--する。
  5. 更新したmiddleとendがそれぞれ前回と同じ値ならば、更にmiddle++, end--する。こうすることで重複を除く事ができる。
  6. 4, 5を(middle < end)が成り立つ間繰り返す。
  7. 以上の処理をstartを0 → arr.length - 3 まで行う。

コレによる計算量はO(N2)となる。

Source Code