18. 4Sum

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        List<List<Integer>> result = new LinkedList<>();
        
        // remember:i<nums.length-3
        for(int i=0; i<nums.length-3; i++){
            if(i==0 || nums[i]>nums[i-1]){
                for(int j=i+1; j<nums.length-2; j++){
                    if(j==i+1 || nums[j]>nums[j-1]){
                        int left = j+1, right=nums.length-1;
                        while(left<right){
                            if(left>j+1 && nums[left]==nums[left-1]){
                                left++;
                            }else if (right<nums.length-1 && nums[right]==nums[right+1]){
                                right--;
                            }else{
                                int sum = nums[i]+nums[j]+nums[left]+nums[right];
                                if(sum==target){
                                    result.add(Arrays.asList(nums[i], nums[j], nums[left],nums[right]));
                                    left++;
                                    right--;
                                }else if(sum>target){
                                    right--;
                                }else{
                                    left++;
                                }
                            }
                        }
                    }
                }
            }
        }
        return result;
    }
}