题目：
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）用递归，先排序，确定第一个，然后确定第二个，再寻找第三个。
packagesum;importjava.util.ArrayList;importjava.util.Arrays;importjava.util.List;publicclassThreeSum {publicList<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> res =newArrayList<List<Integer>>();intlen;if(nums ==null|| (len = nums.length) < 3)returnres;
Arrays.sort(nums);for(inti = 0; i < len - 2; ++i) {intrem = 0 -nums[i];
List<Integer> subRes =newArrayList<Integer>();
subRes.add(nums[i]);
GetTwo(rem, i+ 1, nums, len, subRes, res);//Move forward if next element is the same as current elementwhile(i < len - 1 && nums[i+1] == nums[i]) ++i;
}returnres;
}PRivatevoidGetTwo(intrem,intstart,int[] nums,intlen, List<Integer> subRes, List<List<Integer>>res) {for(inti = start; i < len - 1; ++i) {intlast = rem -nums[i];
List<Integer> cpySubRes =newArrayList<Integer>(subRes);
cpySubRes.add(nums[i]);
GetLast(last, i+ 1, nums, len, cpySubRes, res);//Move forward if next element is the same as current elementwhile(i < len - 1 && nums[i+1] == nums[i]) ++i;
}
}privatevoidGetLast(intrem,intstart,int[] nums,intlen, List<Integer> subRes, List<List<Integer>>res) {for(inti = start; i < len; ++i) {if(rem ==nums[i]) {
subRes.add(nums[i]);
res.add(subRes);
break;
}
}
}publicstaticvoidmain(String[] args) {//TODO Auto-generated method stubThreeSum t =newThreeSum();int[] S = { -1, 0, 1, 2, -1, -4};
List<List<Integer>> res =t.threeSum(S);for(List<Integer>subRes : res) {for(inti : subRes)
System.out.print(i+ "\t");
System.out.println("\n");
}
}
}
2）非递归；排完序之后确立第一个元素，然后用两个指针指向剩下元素的头和尾，两边一夹，然后移动。
packagesum;importjava.util.ArrayList;importjava.util.Arrays;importjava.util.List;publicclassThreeSum {publicList<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> res =newArrayList<List<Integer>>();intlen;if(nums ==null|| (len = nums.length) < 3)returnres;
Arrays.sort(nums);for(inti = 0; i < len - 2;) {intrem = 0 -nums[i];intleft = i + 1;intright = len - 1;while(left <right) {if(nums[left] + nums[right] ==rem) {
List<Integer> subRes =newArrayList<Integer>();
subRes.add(nums[i]);
subRes.add(nums[left]);
subRes.add(nums[right]);
res.add(subRes);//Filter the duplicated elements.do{ ++left; }while(left < len && nums[left] == nums[left - 1]);do{ --right; }while(right >= 0 && nums[right + 1] ==nums[right]);
}elseif(nums[left] + nums[right] <rem) {
left++;
}else{
right--;
}
}//Move forward if the next element is the same as current element.do{ ++i; }while(i < len && nums[i] == nums[i - 1]);
}returnres;
}publicstaticvoidmain(String[] args) {//TODO Auto-generated method stubThreeSum t =newThreeSum();int[] S = { -2,0,1,1,2};
List<List<Integer>> res =t.threeSum(S);for(List<Integer>subRes : res) {for(inti : subRes)
System.out.print(i+ "\t");
System.out.println("\n");
}
}
}