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

Problem

leetcode.com

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

Solution

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

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

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

Source Code