3Sum

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)

 1 import java.util.ArrayList;
 2 import java.util.Arrays;
 3 import java.util.HashSet;
 4 import java.util.List;
 5 import java.util.Set;
 6 
 7 public class Solution {
 8     public static List<List<Integer>> threeSum(int[] nums) {
 9     List<List<Integer>> ans=new ArrayList();
10     Arrays.sort(nums);
11         int len=nums.length;
12         for(int i=0;i<len-2;i++){
13             if(i>0&&nums[i]==nums[i-1]) continue;
14             for(int j=i+1;j<len-1;j++){
15             if(j!=i+1&&nums[j]==nums[j-1]) continue;
16             int sum=nums[i]+nums[j];
17             int res=Search(j+1,len-1,-sum,nums);
18             if(res==-1) continue;
19             ans.add(Arrays.asList(nums[i],nums[j],nums[res]));
20             }
21         }
22     return ans;
23     }    
24     public static int Search(int i,int j,int x,int[]nums){
25     while(i<=j){
26         int mid=(i+j)/2;
27         if(x<nums[mid]){j=mid-1;}
28         else if(x>nums[mid]){i=mid+1;}
29         else return mid;
30     }
31     return -1;
32     }
33     public static void main(String[]args){
34     int[]nums={12,5,-12,4,-11,11,2,7,2,-5,-14,-3,-3,3,2,-10,9,-15,2,14,-3,-15,-3,-14,-1,-7,11,-4,-11,12,-15,-14,2,10,-2,-1,6,7,13,-15,-13,6,-10,-9,-14,7,-12,3,-1,5,2,11,6,14,12,-10,14,0,-7,11,-10,-7,4,-1,-12,-13,13,1,9,3,1,3,-5,6,9,-4,-2,5,14,12,-5,-6,1,8,-15,-10,5,-15,-2,5,3,3,13,-8,-13,8,-5,8,-6,11,-12,3,0,-2,-6,-14,2,0,6,1,-11,9,2,-3,-6,3,3,-15,-5,-14,5,13,-4,-4,-10,-10,11};
35     Arrays.sort(nums);
36     System.out.println(nums.length);
37     List<List<Integer>> ans=threeSum(nums);
38     for(List<Integer> list:ans){
39         for(int x:list){
40         System.out.print(x+",");
41         }
42         System.out.println();
43     }
44     }
45 
46 }