18. 4Sum

在3Sum基础上，固定第一个数对剩下的数进行3Sum
计算，复杂度为O(n^3)

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> zz = new ArrayList<>();
        Arrays.sort(nums);
        int len = nums.length;
        if(len<4)
            return zz;
        for(int i=0;i<len-3;i++){
            while(i!=0&&i<len-3&&nums[i]==nums[i-1])i++;
            for(int j=i+1;j<len-2;j++){
                while(j!=i+1&&j<len-2&&nums[j]==nums[j-1])j++;
                int p = j+1,q = len-1;
                while(p<q){
                    int dis = nums[i]+nums[j]+nums[p]+nums[q]-target;
                    if(dis<0){
                        p++;
                    }else if(dis==0){
                        List<Integer> tmp = new ArrayList<>();
                        tmp.add(nums[i]);
                        tmp.add(nums[j]);
                        tmp.add(nums[p]);
                        tmp.add(nums[q]);
                        zz.add(tmp);
                        p++;
                        q--;
                        while(p<q&&nums[p]==nums[p-1])p++;
                        while(p<q&&nums[q]==nums[q+1])q--;
                    }else{
                        q--;
                    }
                }
            }
        }
        return zz;
    }
}