[数组]18. 4Sum

18. 4Sum
题目大意
给定一个数组，一个target，要求找出所有和为target的四个数的集合，不能重复。

据说还有hashmap法，但效果不如暴力好。

3sum的升级指针法
时间:O(n^3)

左边固定两个指针l1，l2，每次循环＋1
根据和target比较大小，动态调整l3、r指针位置

JAVA: 66 ms

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        Arrays.sort(nums);
        for (int l1 = 0; l1 < nums.length-3; l1++){
            if(l1 > 0 && nums[l1] == nums[l1-1]){
                continue;
            }
            for(int l2 = l1 +1; l2< nums.length-2; l2++){
                if(l2 > l1+1 && nums[l2] == nums[l2 -1]){ //去重 注意：l2从第2个位置开始才和前一比较
                    continue;
                }
                int l3 = l2+1;
                int r = nums.length-1;
                while(l3 < r){
                    int sum = nums[l1] + nums[l2] + nums[l3] +nums[r];
                    if(sum == target){
                        res.add(Arrays.asList(nums[l1], nums[l2], nums[l3], nums[r]));
                        l3++;
                        r--;
                        while(l3 < r && nums[l3]==nums[l3-1]){ //去重
                            l3++;
                        }
                        while(l3 < r && nums[r] == nums[r+1]){
                            r--;
                        }
                    }else if(sum < target){
                        l3++;
                    }else{
                        r--;
                    }
                }
                    
            }
        }
        return res;
    }
}

改进JAVA 33ms
加两个限制条件 就快了很多

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        Arrays.sort(nums);
        for (int l1 = 0; l1 < nums.length-3; l1++){
            if(nums[l1] + nums[l1+1] + nums[l1+2] + nums[l1+3] > target) break;//如果初始已经太大
            if(nums[l1] + nums[nums.length-1] + nums[nums.length-2] + nums[nums.length-3] < target) continue; //第一个元素太小

            if(l1 > 0 && nums[l1] == nums[l1-1]){
                continue;
            }
            for(int l2 = l1 +1; l2< nums.length-2; l2++){
                if(nums[l1] + nums[l2] + nums[l2+1] + nums[l2+2] > target) break; //l2 too large
                if(nums[l1] + nums[l2] + nums[nums.length-1] + nums[nums.length-2] < target) continue; //第一个元素太小

                if(l2 > l1+1 && nums[l2] == nums[l2 -1]){ //去重 注意：l2从第2个位置开始才和前一比较
                    continue;
                }
                int l3 = l2+1;
                int r = nums.length-1;
                while(l3 < r){
                    int sum = nums[l1] + nums[l2] + nums[l3] +nums[r];
                    if(sum == target){
                        res.add(Arrays.asList(nums[l1], nums[l2], nums[l3], nums[r]));
                        l3++;
                        r--;
                        while(l3 < r && nums[l3]==nums[l3-1]){ //去重
                            l3++;
                        }
                        while(l3 < r && nums[r] == nums[r+1]){
                            r--;
                        }
                    }else if(sum < target){
                        l3++;
                    }else{
                        r--;
                    }
                }
                    
            }
        }
        return res;
    }
}