问题描述：

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)

分析：这道题想到了是先排序，然后再用两个指针，left 和right，分别从两端趋近。然后当z=-(Vleft+Vright)，然后在中间搜索z(二分法)。然后用递归的方法，但是却超时了。看了网友的介绍。感觉网友的方法确实很好。

其思想如下：这里有三个变量，因此，向着O(n2)的方向努力。先对数组排序，当数从前向后移动时，固定住一个数，然后再选两个数：left = i+1;right = nums.length-1;然后二者向中间逼近。当Vl+Vr+p>0时，left++l若小于0，right–。当然为0时，添加到list中。

同样，去重也是一个比较讨厌的问题，一个很好的trick是：当num[i]==num[i-1]时，此时固定的数是一样的。那么此时，搜索到的list的集合一定是num[i-1](当p为num[i-1])的子集。所以过滤。

当一个三元组找到之后(num[i],nums[j],num[k])找到时，因为此时为有序排序。所以若num[j+1]==num[j]，过滤。当num[k-1]==num[k]时，过滤。此时，再没有重复的可能。

代码如下：380ms

public class Solution {

public List> threeSum(int[] nums) {

List> res = new LinkedList>();

Arrays.sort(nums);//排序

int i;

int p;

int left,right;

int tmp;

List list;

for(i = 0;i

p = nums[i];

if(i-1>=0&&p==nums[i-1])

continue;

left = i+1;

right = nums.length-1;

while(left

tmp = nums[left]+nums[right]+p;

if(tmp==0){

list = new LinkedList();

list.add(p);

list.add(nums[left]);

list.add(nums[right]);

res.add(list);

while(left+1

left++;

while (right-1>=0&&nums[right-1]==nums[right])

right--;

left++;right--;

}else if(tmp<0)

left++;

else

right--;

}

}

return res;

}

}