# Can anyone give a non-TLE solution?

• I find it seems that the classical O(n^2) solution can't pass because of TLE.

Is there any pruning method or less than O(n^2) method?

The classical solution means that first sort the array and then search the array with three index.

• I think the classical solution can solve the problem.

``````vector<vector<int> > threeSum(vector<int> &num) {

if (num.size()<3) return vector< vector<int> > ();
sort(num.begin(), num.end());
vector< vector<int> > set;
for(int id=0; id<num.size()-2; id++) {
int ids = id+1, ide = int(num.size())-1;
while(ids<ide && ids<num.size() && ide>=0) {
if (num.at(ids) + num.at(ide) + num.at(id) == 0) {
vector<int> ans(3, 0);
ans.at(0) = num.at(id); ans.at(1) = num.at(ids);
ans.at(2) = num.at(ide);
set.push_back(ans);
ids++; ide--;
while(ids<num.size() && (num.at(ids-1) == num.at(ids)))
ids++;
while(ide>id && (num.at(ide+1) == num.at(ide)))
ide--;
}
else if (num.at(ids) + num.at(ide) + num.at(id) > 0)
ide--;
else ids++;
}
while((id+1)<int(num.size()) && (num.at(id+1) == num.at(id)))
id++;
}
return set;

}``````

• The simple O(n^2) solution will TLE. We need to do some prune for duplicated numbers. For the middle number of triplet, if it is the same to the previous two, then it can be skipped (the previous one is equivalent to it). Similar to the first and third element, we can also skip some elements, to reduce the time we need to judge duplicate of result.

``````vector<vector<int> > threeSum(vector<int> &num) {
vector<vector<int> > result;
int n = (int)num.size();
if (n > 2) {
sort(num.begin(), num.end());

for (int i = 1; i < n - 1; ++i) {
if (i > 2 && num[i] == num[i - 2]) continue;
int l = 0, r = n - 1;
while (l < i && r > i) {
if (l > 1 && num[l] == num[l - 1]) {
++l; continue;
}
if (r < n - 1 && num[r] == num[r + 1]) {
--r; continue;
}
int sum = num[l] + num[i] + num[r];
if (sum == 0) {
vector<int> item { num[l], num[i], num[r] };
bool flag = false;
for (int j = 0; j < result.size(); ++j) {
if (result[j][0] == num[l] && result[j][1] == num[i]) {
flag = true; break;
}
}
if (!flag) result.push_back(item);
++l; --r;
} else if (sum < 0) ++l; else --r;
}
}
}
return result;
}``````

• Of course the O(N^2) should pass the TLE. The only thing you need to do is to remove the duplication during your O(N^2) process to save more time

``````public List<List<Integer>> threeSum(int[] num) {
// two pointer runner solution O(N^2 + NlogN)
if (num.length < 3) return new ArrayList<List<Integer>>();
Arrays.sort(num);
List<List<Integer>> triplets = new ArrayList<>();
for (int i = 0; i < num.length - 1; ) {
int j = i + 1;
int k = num.length - 1;
while (j < k) {
int sum = num[i] + num[j] + num[k];
// remove duplication when you move i,j or k
if (sum > 0) while (num[k] == num[--k] && num[j] <= num[k] && j < k);
else if (sum < 0) while (num[j] == num[++j] && num[j] <= num[k] && j < k);
else {
ArrayList<Integer> list = new ArrayList<>();
while (num[k] == num[--k] && num[j] <= num[k] && j < k);
while (num[j] == num[++j] && num[j] <= num[k] && j < k);
}
}
while (num[i] == num[++i] && i < num.length - 2);
}
return triplets;
}``````

• Hi renli3000, since the array is already sorted, j < k guarantees num[j] <= num[k], right?

• Here's a solution in java using hashmap. surprising simple... the key is sorting help skipping all duplicates , that help in two ways. 1) reduciung further the processing time 2) skip duplicated output. the hashmap only keeps the largest index with same value, so the size will be small too.

``````HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>();

Arrays.sort(num);
for (int i = 0; i< num.length; i++) hm.put(num[i], i);
for (int i = 0; i<num.length; i++){
if (i > 0 && num[i] == num[i-1]) continue;
for (int j = i+1; j<num.length; j++){
if (j > i+1 && num[j] == num[j-1]) continue;
if (hm.containsKey(0-num[i] - num[j])){
if (hm.get(0-num[i]-num[j]) > j){
// we found a match
}

}
}
}
return llll;

}``````

• I guess my code is somewhat easier to understand.

``````public class Solution {
public List<List<Integer>> threeSum(int[] num) {
if (num==null||num.length<3) return results;

Arrays.sort(num);
for (int i = 0; i < num.length-2; i++) {
if (i>0&&num[i]==num[i-1]) continue;	//Avoid Duplicates
int target=-num[i];
int j=i+1;
int k=num.length-1;
while (j<k){
if (j>i+1&&num[j]==num[j-1]){
j++;
continue;//Avoid Duplicates
}
if (k<num.length-1&&num[k]==num[k+1]){
k--;
continue;//Avoid Duplicates
}
if ((num[j]+num[k])>target)
k--;
else if ((num[j]+num[k])<target)
j++;
else