配列における3つの要素の和
Problem
与えられた配列において、任意の3点の和がゼロとなる組合せを全て取得する問題。
Solution
この問題は以下のように解くことができる。
- 任意の3点をstart, middle, endと置く(start < middle < end)
- startを固定し、
middle = start + 1
,end = arr.length - 1
と置く - 上記により3点が決まるので、3点の和を計算し
s
と置く s == sum
ならば、その要素達をリストに追加。この時、middle++
,end--
する。- 更新したmiddleとendがそれぞれ前回と同じ値ならば、更に
middle++
,end--
する。こうすることで重複を除く事ができる。 - 4, 5を(middle < end)が成り立つ間繰り返す。
- 以上の処理をstartを0 → arr.length - 3 まで行う。
コレによる計算量はO(N2)となる。