3Sum

public class {
  public List<List<Integer>> threeSum(int[] nums){
    Arrays.sort(nums);
    List<List<Integer>> res = new LinkedList<>();
    for(int i=0; i < nums.length - 2; i++){
      
      //如果用nums[i] ！= nums[i+1]，则会漏掉-1，-1，2这种情况
      if(i == 0 ||(i>0 && nums[i] != nums[i-1])){
        int begin = i+1,end = nums.length-1,sum = 0 - nums[i];//sum = 0-nums[i]将三个数求和编程两个数求和来处理，这种方法经常用
        while(begin < end){
        if(nums[begin]+nums[end] == sum){
          	res.add(Arrays.asList(nums[i],nums[begin],nums[end]));
          while(begin < end && nums[begin] == nums[begin+1])
            begin++;
          while(begin < end && nums[end] == nums[end-1])
            end--;
          begin++;
          end--;
        }else if(nums[begin] + nums[end] < sum){
          begin++;
        }else{
          end--;
        }
      }
     }
    }
    return res;
  }
}