18. 4Sum
題目大意
給定一個(gè)數(shù)組，一個(gè)target，要求找出所有和為target的四個(gè)數(shù)的集合，不能重復(fù)。

據(jù)說還有hashmap法，但效果不如暴力好。

3sum的升級(jí)指針法
時(shí)間:O(n^3)

左邊固定兩個(gè)指針l1，l2，每次循環(huán)＋1
根據(jù)和target比較大小，動(dòng)態(tài)調(diào)整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個(gè)位置開始才和前一比較
                    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;
    }
}

改進(jìn)JAVA 33ms
加兩個(gè)限制條件 就快了很多

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;//如果初始已經(jīng)太大
            if(nums[l1] + nums[nums.length-1] + nums[nums.length-2] + nums[nums.length-3] < target) continue; //第一個(gè)元素太小

            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; //第一個(gè)元素太小

                if(l2 > l1+1 && nums[l2] == nums[l2 -1]){ //去重 注意：l2從第2個(gè)位置開始才和前一比較
                    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;
    }
}