# Get Time out for O(n^2) method

• Any suggestion for my code, I think it only loop twice. So it should be O(n^2)

``````  public class Solution {
public List<List<Integer>> threeSum(int[] num) {
//  record the result
List<List<Integer>> allSumlist=new ArrayList<List<Integer>>();
if (num.length<3) {return allSumlist;}
// hashmap to record all element with index for this element in the array num
HashMap<Integer, ArrayList<Integer>> numSet=new HashMap<Integer, ArrayList<Integer>>();
// record all elements into this hashMap
for (int i=0; i<num.length; i++) {
else {
ArrayList<Integer> newIndex=new ArrayList<Integer>();
numSet.put(num[i], newIndex);
}
}

//  double loop, check the third one using hashmap, if the index of this element is greater than j, we get a solution and add it to our result
for (int i=0; i<num.length-2; i++) {
for (int j=i+1; j<num.length-1; j++) {
int k= 0-num[i]-num[j];
if (numSet.containsKey(k)) {
for (int x : numSet.get(k) ) {
//  if the third element index is greater than j, then we find a solution
if (x>j) {
ArrayList<Integer> newSumSet=new ArrayList<Integer>();
}
}

}
}

}

return allSumlist;

}
``````

}

• I have similar code with you and also got time limit problem. The reason I think is that this code could have a worst case complexity of O(n^3) when there are a lot of array elements with the same value.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.