题目：

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) 题解：  3 Sum是two Sum的变种，可以利用two sum的二分查找法来解决问题。  本题比two sum增加的问题有：解决duplicate问题，3个数相加返回数值而非index。  首先，对数组进行排序。  然后，从0位置开始到倒数第三个位置（num.length-3)，进行遍历，假定num[i]就是3sum中得第一个加数，然后从i+1的位置开始，进行2sum的运算。  当找到一个3sum==0的情况时，判断是否在结果hashset中出现过，没有则添加。(利用hashset的value唯一性）  因为结果不唯一，此时不能停止，继续搜索，low和high指针同时挪动。  时间复杂度是O(n2)  实现代码为：

 1     

public ArrayList<ArrayList<Integer>> threeSum(

int[] num) {

 2         ArrayList<ArrayList<Integer>> res = 

new ArrayList<ArrayList<Integer>>();

 3         

if(num.length<3||num == 

null)

 4             

return res;

 5         

 6         HashSet<ArrayList<Integer>> hs = 

new HashSet<ArrayList<Integer>>();

 7         

 8         Arrays.sort(num);

 9         

10         

for(

int i = 0; i <= num.length-3; i++){

11             

int low = i+1;

12             

int high = num.length-1;

13             

while(low<high){

//

since they cannot be the same one, low should not equal to high

14 

                

int sum = num[i]+num[low]+num[high];

15                 

if(sum == 0){

16                     ArrayList<Integer> unit = 

new ArrayList<Integer>();

17                     unit.add(num[i]);

18                     unit.add(num[low]);

19                     unit.add(num[high]);

20                     

21                     

if(!hs.contains(unit)){

22                         hs.add(unit);

23                         res.add(unit);

24                     }

25                     

26                     low++;

27                     high--;

28                 }

else 

if(sum > 0)

29                     high --;

30                  

else

31                     low ++;

32             }

33         }

34         

35         

return res;

36     }

同时，解决duplicate问题，也可以通过挪动指针来解决判断，当找到一个合格结果时，将3个加数指针挪动到与当前值不同的地方，才再进行继续判断，代码如下：

 1     

public ArrayList<ArrayList<Integer>> threeSum(

int[] num) {

 2         ArrayList<ArrayList<Integer>> res = 

new ArrayList<ArrayList<Integer>>();

 3         

if(num.length<3||num == 

null)

 4             

return res;

 5         

 6         Arrays.sort(num);

 7         

 8         

for(

int i = 0; i <= num.length-3; i++){

 9             

if(i==0||num[i]!=num[i-1]){

//

remove dupicate

10 

                

int low = i+1;

11                 

int high = num.length-1;

12                 

while(low<high){

13                     

int sum = num[i]+num[low]+num[high];

14                     

if(sum == 0){

15                         ArrayList<Integer> unit = 

new ArrayList<Integer>();

16                         unit.add(num[i]);

17                         unit.add(num[low]);

18                         unit.add(num[high]);

19                         

20                         res.add(unit);

21                         

22                         low++;

23                         high--;

24                         

25                         

while(low<high&&num[low]==num[low-1])

//

remove dupicate

26 

                            low++;

27                         

while(low<high&&num[high]==num[high+1])

//

remove dupicate

28 

                            high--;

29                             

30                     }

else 

if(sum > 0)

31                         high --;

32                      

else

33                         low ++;

34                 }

35             }

36         }

37         

return res;

38     }