4Sum (Leet Code Java Solution)

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]
]

Solution:-

public class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        
        Map<String , Integer> map =  new HashMap<String, Integer>();
        
        HashSet<List<Integer>> set = new HashSet<List<Integer>>();
        
        for(int t = 0 ; t < nums.length - 3 ; t++){
            for(int i = t+1 ; i < nums.length - 2 ; i++){
            
            int start = i + 1 ;
            int end = nums.length - 1;
            
            while(start < end){
                
                if(nums[t] + nums[i] + nums[start]+ nums[end] == target){
                    List<Integer> temp = new ArrayList<Integer>();
                    temp.add(nums[t]);
                    temp.add(nums[i]);
                    temp.add(nums[start]);
                    temp.add(nums[end]);
                    set.add(temp);
                    start++;
                    end--;
                }
                else{
                if(nums[t] + nums[i] + nums[start]+ nums[end] < target){
                    start++;
                }
                else{
                    end--;
                }
                }
            }
            }
        }
        res.addAll(set);
        return res;
    }

}