LeetCode 3Sum Time Limit Exceeded

Question

So I am trying to complete Leetcode's 3Sum problem. My solution gets the correct answer, however with longer testcases I get "Time Limit Exceeded". I'm guessing this is because of the nested for loops I am using but am not sure how to proceed from here.

class Solution {
public List<List<Integer>> threeSum(int[] nums) {
    int x = 0;
    int y = 0;
    int z = 0;
    Arrays.sort(nums);
    List<List<Integer>> res = new ArrayList<>();


    Map<Integer,Integer> map = new HashMap();

    for (int i = 0; i < nums.length; i++){
        map.put(i, nums[i]);
    }

    for (int j = 0; j < nums.length - 2; j++){
        x = map.get(j);
        for(int k = j+1;k < nums.length - 1; k++){
            y = map.get(k);
            for(int l = k+1; l <nums.length; l++){
                z = map.get(l);
                if((x + y + z) == 0){
                    List<Integer> triplet = new ArrayList<Integer>();
                    triplet.add(x);
                    triplet.add(y);
                    triplet.add(z);
                    System.out.println(triplet);
                    if (!(res.contains(triplet))){
                        res.add(triplet);
                    }

                }
            }
        }
    }
    return res;
}

Any tips on how to optimize this solution?

Answer 1

Your solution is O(N^3). Hence, getting Time Limit Exceed.

The question can be solved more effiiently as shown below:

public List<List<Integer>> threeSum(int[] num) {
    Arrays.sort(num);
    List<List<Integer>> res = new LinkedList<>(); 
    for (int i = 0; i < num.length-2; i++) {
        if (i == 0 || (i > 0 && num[i] != num[i-1])) {
            int lo = i+1, hi = num.length-1, sum = 0 - num[i];
            while (lo < hi) {
                if (num[lo] + num[hi] == sum) {
                    res.add(Arrays.asList(num[i], num[lo], num[hi]));
                    while (lo < hi && num[lo] == num[lo+1]) lo++;
                    while (lo < hi && num[hi] == num[hi-1]) hi--;
                    lo++; hi--;
                } else if (num[lo] + num[hi] < sum) lo++;
                else hi--;
           }
        }
    }
    return res;
}

Answer 2

Below is the approach I followed and able to submit to leetcode

public List<List<Integer>> threeSum(int[] nums){   
  Arrays.sort(nums);
  List<List<Integer>> result = new ArrayList<List<Integer>>();
 
  for(int i = 0; i < nums.length - 1; i++) {  
    if(i == 0 || (i > 0  && nums[i] != nums[i-1])) { 
      int left = i+1, right = nums.length -1 ;
       while(left < right) {  
        int sum = nums[i] + nums[left] + nums[right];
         if(sum  > 0 ){ 
          right -=1;
         } else if(sum < 0) {  
          left +=1; 
         } else { 
          result.add(Arrays.asList(nums[i], nums[left], nums[right]));
          left += 1;
          while(left < right  && nums[left] == nums[left -1]) {  
          i +=1; 
          }
         }
      } 
   }  
}
return result;
}