leetcode-18. 四数之和

不解释了，直接上代码，代码详细注释。

class Solution {
    public List> fourSum(int[] nums, int target) {
    //使用双指针法，首先排序
        Arrays.sort(nums);
        List> res = new LinkedList<>();
        for(int i = 0; i < nums.length; ++i){
           
            List> tmp = threeSum(nums, i + 1, target - nums[i]);
            for(List tuple : tmp){
                tuple.add(nums[i]);
                res.add(tuple);
            }
            //下面这个while为什么不能放到前面呢？
            //因为先找第一个数是target的三元组，如果先把指针移动到最后一个相同元素去寻找，
            //那么结果中将缺少，含有相同元素，但是正确答案的三元组。
            while(i < nums.length - 1 && nums[i] == nums[i + 1]) i++;
        }
        return res;
    }
    //3sum问题
      public List> threeSum(int[] nums, int start, int target) {
        
        List> res = new LinkedList<>();
        for(int i = start; i < nums.length; ++i){
           
            List> tmp = twoSum(nums, i + 1, target - nums[i]);
            for(List tuple : tmp){
                tuple.add(nums[i]);
                res.add(tuple);
            }
            //下面这个while为什么不能放到前面呢？
            //因为先找第一个数是target的三元组，如果先把指针移动到最后一个相同元素去寻找，
            //那么结果中将缺少，含有相同元素，但是正确答案的三元组。
            while(i < nums.length - 1 && nums[i] == nums[i + 1]) i++;
        }
        return res;
    }
    //twoSum问题
    public List> twoSum(int[] nums, int start,int  target){
        int lo = start;
        int rh = nums.length - 1;
        List> res = new LinkedList<>();     
        while(lo < rh){
            int left = nums[lo];
            int right = nums[rh];
            int sum = nums[lo] + nums[rh];
            if(sum < target){
                //这里所有的while都是为了去重。
                //例如：1， 2， 2，3    使用了2后，要移动到3.
                while(lo < rh && nums[lo] == left) lo ++;
            }else if(sum > target){
                while(lo < rh && nums[rh] == right) rh --;
            }else{
                List tmp = new LinkedList<>();
                tmp.add(left);
                tmp.add(right);
                res.add(tmp);
                while(lo < rh && nums[lo] == left) lo ++;
                while(lo < rh && nums[rh] == right) rh --;
            }
        }
        return res;
    }
}