18. 4Sum

Medium

Given an array nums of n integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:

• 0 <= a, b, c, d < n
• a, b, c, and d are distinct.
• nums[a] + nums[b] + nums[c] + nums[d] == target

You may return the answer in any order. 

Example 1:

Input: nums = [1,0,-1,0,-2,2], target = 0
Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

Example 2:

Input: nums = [2,2,2,2,2], target = 8
Output: [[2,2,2,2]]

Constraints:

• 1 <= nums.length <= 200
• -109 <= nums[i] <= 109
• -109 <= target <= 109


class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        List<List<Integer>> list = new ArrayList();
        for(int a=0;a<nums.length-3;a++){
            if(a>0 && nums[a]==nums[a-1]) continue;
            for(int b=a+1;b<nums.length-2;b++){
                if(b>a+1 && nums[b]==nums[b-1]) continue;
                int temp = target-nums[a]-nums[b];
                int left = b+1;
                int right = nums.length-1;
                while(left<right){
                    if(nums[left]+nums[right]==temp){
                        list.add(Arrays.asList(nums[a],nums[b],nums[left],nums[right]));
                        left++;right--;
                        while(left<right && nums[left]==nums[left-1]) left++;                        
                        while(left<right && nums[right]==nums[right+1]) right--;                                                
                    }
                    else if(nums[left]+nums[right]<temp){
                        left++;
                        while(left<right && nums[left]==nums[left-1]) left++;                        
                    }
                    else{
                        right--;
                        while(left<right && nums[right]==nums[right+1]) right--;                                                
                    }
                }
            }
        }
        return list;
    }
}