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: The solution set must not contain duplicate triplets.
Example
For example, given array S = [-1,0,1,2,-1,-4],
A solution set is:
[
[-1,0,1],
[-1,-1,2]
]
解题思路：
这道题看起来跟leetcode-1的思路差不多，第一题是求解a+b = target，这一道题是求解a+b+c = target。将式子转换为b+c = target - a，就跟leetcode-1那道题是一样的了。
相比于leetcode-1，这道题不需要记住数组中每个值的下标，而且返回的数组是从小到大排列的，因此可以用Arrays.sort(()先对数组进行排序，这样方便下面的操作。
进行排序之后，用for循环获得值a，此时b+c = target - a，在a之后的值中找到b跟c就可，思路同leetcode-1。
不过这道题有一个要点就是，有可能出现多个相同的结果，例如对于S = [0,0,0,0]，直接查找可能返回[ [0,0,0] , [0,0,0] ]，对于S = [-2,0,2,2]，可能返回[ [-2,0,2] , [-2,0,2] ] ，与要求不符，由于我们的数组已经经过了排序，所以在选择a的时候（a的下标为i），如果S[i] == S[i-1]，直接跳过，当找到满足的a+b+c = 0之后（默认a<b<c），跳过与c相同的值继续进行查找，这样可以防止出现多组相同的结果。 另外一个要点就是，当a的值已经大于0时，结束查找，返回结果。
[java] view plain copy print ? import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.HashSet; import java.util.List; public class Solution { public List<List<Integer>> threeSum(int[] nums) { List<List<Integer>> answerList = new ArrayList<List<Integer>>(); //对数组进行排序 Arrays.sort(nums); int len = nums.length; for(int i = 0;i<len;i++) { //获取a = nums[i]，调整target int target = 0-nums[i]; //当a大于0时，结束查找 if(target <0) break; //当a与前一个值相同时，该值，查找下一个值 if(i>0 && (nums[i] == nums[i-1])) continue; HashSet<Integer> numSet = new HashSet<Integer>(); int j = i+1; while(j < len) { //获取c值 int num1 = nums[j]; //得到对应的b值 int num2 = target - num1; j++; //查找成功 if(numSet.contains(num2)) { List<Integer> answer = new ArrayList<Integer>(); answer.add(-target); answer.add(num2); answer.add(num1); answerList.add(answer); //找到下一个与当前c不同的值，继续循环 while(j<len && nums[j] == num1) j++; } numSet.add(num1); } } return answerList; } import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.HashSet; import java.util.List; public class Solution { public List<List<Integer>> threeSum(int[] nums) { List<List<Integer>> answerList = new ArrayList<List<Integer>>(); //对数组进行排序 Arrays.sort(nums); int len = nums.length; for(int i = 0;i<len;i++) { //获取a = nums[i]，调整target int target = 0-nums[i]; //当a大于0时，结束查找 if(target <0) break; //当a与前一个值相同时，该值，查找下一个值 if(i>0 && (nums[i] == nums[i-1])) continue; HashSet<Integer> numSet = new HashSet<Integer>(); int j = i+1; while(j < len) { //获取c值 int num1 = nums[j]; //得到对应的b值 int num2 = target - num1; j++; //查找成功 if(numSet.contains(num2)) { List<Integer> answer = new ArrayList<Integer>(); answer.add(-target); answer.add(num2); answer.add(num1); answerList.add(answer); //找到下一个与当前c不同的值，继续循环 while(j<len && nums[j] == num1) j++; } numSet.add(num1); } } return answerList; } 看了下leetcode里面点赞最高的那个，其实也可以不用用HashSet来存储数据的，在计算两个数之和的时候，利用夹逼的方式去求得所有满足的解就可以了。这样还能够减少空间复杂度。当时也是没有想得那么周全。
