public class S018 {

    //借鉴S015，速度有些慢

    public List<List<Integer>> fourSum(int[] nums, int target) {

        Arrays.sort(nums);

        List<List<Integer>> result = new ArrayList<List<Integer>>();

        for(int i =0;i<nums.length-3;i++){

            if(i>0&&nums[i]==nums[i-1]){

                continue;//重复的直接跳过

            }

            for(int j = i+1;j<nums.length-2;j++){

                if(j>i+1&&nums[j]==nums[j-1]){

                    continue;//重复的直接跳过

                }

                int left = j+1;//从i+1开始也是防止重复的办法

                int right = nums.length-1;

                while(left<right){

                    if(nums[left]+nums[right]+nums[i]+nums[j] == target){

                        List<Integer> temp = new ArrayList<Integer>();//必须每次新建

                        temp.add(nums[i]);

                        temp.add(nums[left]);

                        temp.add(nums[right]);

                        temp.add(nums[j]);

                        Collections.sort(temp);

                        result.add(temp);

                        //特别注意下面两个while循环

                        left++;

                        right--;//防止重复

                        while(left<right&&nums[left]==nums[left-1]){

                            left++;//防止重复

                        }

                        while(left<right&&nums[right]==nums[right+1]){

                            right--;//防止重复

                        }

                        //这两个条件特别重要，思考一下为何分别是left++和right--;

                    }else if(nums[left]+nums[right]+nums[i]+nums[j]<target){

                        left++;

                    }else{

                        right--;

                    }

                }

            }

        }

        return result;

    }

}