18. 4Sum QuestionEditorial Solution My Submissions

Total Accepted: 80129 Total Submissions: 327682 Difficulty: Medium Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note: The solution set must not contain duplicate quadruplets.

For example, given array S = [1, 0, -1, 0, -2, 2], and target = 0.

A solution set is: [ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2] ]

the key point here is how to step over the duplicates.

public class Solution {
    // this question is about how to remove duplicates

    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> fourSum(int[] nums, int target) {

            if(nums == null || nums.length == 0) return res;

            Arrays.sort(nums);

            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 l = j+1;
                    int r = nums.length-1;

                    while(l < r){
                        int sum = nums[i] + nums[j] + nums[l] + nums[r];
                        if(sum == target){
                            List<Integer> list = new ArrayList<>();
                            list.add(nums[i]);
                            list.add(nums[j]);
                            list.add(nums[l]);
                            list.add(nums[r]);
                            res.add(list);
                            l++;
                            r--;
                            while(l<r && nums[l] == nums[l-1]) l++;
                            while(l<r && nums[r] == nums[r+1]) r--;
                        }else if(sum < target){
                            l++;
                        }else{
                            r--;
                        }

                    }
                }
            }
            return res;
    }
}
`