[LeetCode] 4Sum

Question:

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.

Thoughts : similar with the 3Sum

Java Code:

public List> fourSum(int[] num, int target) {
           Arrays.sort(num);
           List> res = new ArrayList>();
           
           for(int i = 0; i < num.length - 3; i++){
               for(int j = i+1; j < num.length - 2; j++){
                   int start = j+1, end = num.length - 1;
                   
                   while(start < end){
                       int total = num[i] + num[j] + num[start] + num[end];
                       
                       if(total == target){
                           List tmp = new ArrayList();
                           tmp.add(num[i]);
                           tmp.add(num[j]);
                           tmp.add(num[start]);
                           tmp.add(num[end]);
                           
                           res.add(tmp);
                       }
                       
                       if(total >= target){
                           end--;
                           while(end > start && num[end] == num[end+1]) end--;
                       }
                       
                        if(total <= target){
                           start++;
                           while(end > start && num[start] == num[start-1]) start++;
                       }
                   }
                   
                   while(j < num.length -2 && num[j] == num[j+1]) j++;
               }
               
               while(i < num.length - 3 && num[i] == num[i+1]) i++;
           }
           
           return res;
    }