Related Topics：[Array][Two Pointers]
Similar Questions:[Two Sum][3Sum Closest][4Sum][3Sum Smaller]
题目：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)
思路：这道题与Leetcode[1]Two Sum相似，不同的是该题要求返回的是值而不是索引，因此可以先对数组进行排序。然后对数组元素从第一个遍历到倒数第三个，对检查到的元素之后的元素采用标准双向2Sum扫描，sum为0-当前元素值，设置两个指针，分别从剩余元素左右两端开始扫描，当指针所指元素之和小于sum，则左指针右移，当大于sum，则右指针左移。要注意跳过相同的元素，避免重复解。
java解法1：
class Solution {
public List<List<Integer>> threeSum(int[] num) {
List<List<Integer>> res=new LinkedList<>();
Arrays.sort(num);
int i=0;
while(i<num.length-2) {
//当与前一个元素相同时，跳过该元素的检查。
if(i==0||(i!=0&&(num[i]!=num[i-1]))) {
int lo=i+1;
int hi=num.length-1;
int sum=0-num[i];
while(lo<hi){
if(num[lo]+num[hi]==sum) {
res.add(Arrays.asList(num[i],num[lo],num[hi]));
lo++;hi--;
//如果该元素与前（后）一元素相同，则跳过元素
while(lo<hi&&num[lo]==num[lo-1]) lo++;
while(lo<hi&&num[hi]==num[hi+1]) hi--;
}else if(num[lo]+num[hi]<sum) {
lo++;
}else hi--;
}
}
i++;
}
return res;
}
}
