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相似，不同的是該題要求返回的是值而不是索引，因此可以先對(duì)數(shù)組進(jìn)行排序观挎。然后對(duì)數(shù)組元素從第一個(gè)遍歷到倒數(shù)第三個(gè)萧芙，對(duì)檢查到的元素之后的元素采用標(biāo)準(zhǔn)雙向2Sum掃描谚中，sum為0-當(dāng)前元素值，設(shè)置兩個(gè)指針，分別從剩余元素左右兩端開(kāi)始掃描，當(dāng)指針?biāo)冈刂托∮趕um嘱函，則左指針右移，當(dāng)大于sum埂蕊，則右指針左移往弓。要注意跳過(guò)相同的元素，避免重復(fù)解蓄氧。
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) {
//當(dāng)與前一個(gè)元素相同時(shí)函似，跳過(guò)該元素的檢查。
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--;
//如果該元素與前（后）一元素相同喉童，則跳過(guò)元素
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;
}
}
