https://leetcode.com/problems/3sum/

Given an arraySofnintegers, are there elementsa,b,cinSsuch thata+b+c= 0? Find all unique triplets in the array which gives the sum of zero.

Note:The solution set must not contain duplicate triplets.

How to convert from 3sum to 2sum

fix one number.

for example: one + two + three = sum

one is from num[0] ... num[n - 3]

two is from num[1] ... num[n - 2]

three is from num[2] ... num[n - 1]

What we need to do is just fix the one, then select two and three from the numbers at the right side of one

eg. now one is num[i] so we can convert to 2sum from num {i + 1, ... , n - 1}

这里的难点是怎么remove duplicates

1. keep a set/map, always check it before we insert into final result list.
2. for a sorted array, 我们把one，two， three 看做三个位置，我们往这三个位置填数字，因为是顺序遍历 我们对每个位置，每个数只往某个位置填一次。That to say, 如果array 中 有 n 个 i， 我们只往one 中填一次i，对于之后的 i， 我们都跳过。对于two and three 也是一样。
3. 但是这里要注意的是 比如[0, 0, 0, 0]. our target is 0. one 只会用第一个 0， 但是对于two，第二0在它看来是第一个可填的0. 因此 我们这里说的只填一次是每一个可填数字的第一个 ==>

while (index > lower_bound && num[index] == num[index - 1]) continue;

假如我们保证了第一个 和 第二数不重复 那么第三个一定不会重复