【LeetCode】18. 4Sum（中等难度）

和15题非常非常类似

参照第15题的解法。

class Solution {
    public List> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        List> res = new linkedList<>();
        for(int i = 0; i < nums.length - 3; i++){
            if(i == 0 || (i > 0 && nums[i] != nums[i-1])){
                for(int j = i + 1; j < nums.length - 2; j++){
                    if(j == i + 1 || (nums[j] != nums[j-1])){
                        int l = j + 1, h = nums.length - 1, sum = target - nums[i] - nums[j];
                        while(l < h){
                            if(nums[l] + nums[h] == sum){
                                res.add(Arrays.asList(nums[i], nums[j], nums[l], nums[h]));
                                while(l < h && nums[l] == nums[l+1]) l++;
                                while(l < h && nums[h] == nums[h-1]) h--;
                                l++;
                                h--;
                            }else if(nums[l] + nums[h] < sum){
                                l++;
                            }else{
                                h--;
                            }
                        }
                    }
                }
            }
        }
        return res;
    }
}