[LeetCode] 4Sum

Problem:

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:

• Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a ≤ b ≤ c ≤ d)
• 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: AcceptableO(n^3)

public class Solution {
    public ArrayList<ArrayList<Integer>> fourSum(int[] num, int target) {
      ArrayList<ArrayList<Integer>> list = new ArrayList<>();
      
      if( num == null || num.length <4)
        return list;
      Arrays.sort(num);
      HashMap<ArrayList<Integer>,Boolean> map = new HashMap<>();
      for(int i=0; i<num.length;i++){
          for(int j=i+1; j<num.length;j++){
              int s2 = num[i]+num[j];
              int aim = target - s2;
              int start = j+1;
              int end = num.length-1;
              while(start<end){
                  if(num[start] + num[end]  == aim){
                      ArrayList<Integer> slist = new ArrayList<>();
                      slist.add(num[i]);
                      slist.add(num[j]);
                      slist.add(num[start]);
                      slist.add(num[end]);
                      if(map.get(slist) == null){
                      list.add(slist);
                      map.put(slist,true);
                      }
                      start++;
                      end--;
                  }else if(num[start] + num[end] < aim){
                      start++;
                  }else{
                      end--;
                  }
              }
          }
      }
      return list;
  }
}

Key Concept: We can use two sum concept and reduce complexity to O(n*n*logn)