LeetCode18：四数之和

题目描述：

解题思路：

1、排序，根据三数之和的经验，首先对数组排序，这样的很话，确定第一个数字之后，就可以将本题转化成类似三数之和那种的；

2、固定第一个元素，将该题转化为三数之和问题。

具体代码：

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        int len = nums.length;
        List<List<Integer>> res = new ArrayList<>();
        if(len < 4 || nums == null) return res;
        Arrays.sort(nums); // 对数组排序
        for(int i = 0; i < len - 3; i++){ // 固定第一个元素
            if(i > 0 && nums[i] == nums[i-1]) continue; // 防止因为元素重复导致答案一样
            int min1 = nums[i] + nums[i+1] + nums[i+2] + nums[i+3]; 
            int max1 = nums[i] + nums[len-1] + nums[len-2] + nums[len-3];// 快速判断target是否不存在，target可能存在的条件是min1 < target < max1
            if(min1 > target || max1 < target){
                continue;
            }
            for(int j = i + 1; j < len -2; j++){ // 固定第二个元素
                if(j  > i + 1 && nums[j] == nums[j-1]) continue; // 防止结果重复
                int k = j + 1;
                int l = len - 1;
                while(k < l){ // 双指针寻找另外两个数
                    int sum = nums[i] + nums[j] + nums[k] + nums[l];
                    if(sum < target){
                        k++;
                    }else if(sum > target){
                        l--;
                    }else{ // 将和为target的四个数存到结果中
                        ArrayList<Integer> temp = new ArrayList<>();
                        temp.add(nums[i]);
                        temp.add(nums[j]);
                        temp.add(nums[k]);
                        temp.add(nums[l]);
                        res.add(temp);
                        k++;
                        l--; // 直接移动指针
                        while(k < l && nums[k] == nums[k-1]){ //防止元素重复引起结果重复
                            k++;
                        }
                        while(k < l && nums[l] == nums[l+1]){
                            l--;
                        }
                    }
                }
            }
        }
        return res;
    }
}