3Sum

Problem

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:
Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)
The solution set must not contain duplicate triplets.

For example, given array S = {-1 0 1 2 -1 -4},
A solution set is:
(-1, 0, 1)
(-1, -1, 2)

---

Idea

• 先排序，然后假定第一个元素，让这个元素start从num[0]到num[n-2]遍历。
• 采用两边夹逼的方法，定义两个变量，mid 和 end. 比较start+mid+end和0的关系，若小于0则mid++，大于0则end--

---

Note

• vector<vector<int> > a的用法
首先这个多维的数组被写做 vector<vector<int>空格>. 其实是描述了一个二维数组/矩阵 a。其初始化可以参考下面的代码
• Sort the vector by STL

---

Solution

---