# TLE with both o(n2) methods need help!

• here's my regular O(n2) method:

``````class Solution:
# @return a list of lists of length 3, [[val1,val2,val3]]
def threeSum(self, num):
if len(num) < 3:
return []
num.sort()
result = []
for k in range(1, len(num) - 1):
i = 0
j = len(num) - 1
while i < k and j > k:
if num[i] + num[j] == -num[k]:
if not [num[i],num[k],num[j]] in result:
result.append([num[i],num[k],num[j]])
while num[i] == num[i + 1] and i < k:
i += 1
while num[j] == num[j - 1] and j > k:
j -= 1
i += 1
j -= 1
elif num[i] + num[j] < -num[k]:
while num[i] == num[i + 1] and i < k:
i += 1
i += 1
else:
while num[j] == num[j - 1] and j > k:
j -= 1
j -= 1
return result
``````

I have even tried to improve it using binary search

``````class Solution:
# @return a list of lists of length 3, [[val1,val2,val3]]
def threeSum(self, num):
if len(num) < 3:
return []
num.sort()
result = []
for k in range(1, len(num) - 1):
i = 0
j = len(num) - 1
self.rec(num,i,k,j,result,True)

return result

def rec(self, num,i,k,j,result, is_left):
if i >= k or j <= k:
return
if is_left:
tmpRe = self.binary(num, -num[i] - num[k] ,k+1,j)
if tmpRe == -1:
while num[i] == num[i + 1] and i < k:
i += 1
i += 1
self.rec(num, i,k, j,result,True)
else:
j = tmpRe
if not [num[i],num[k],num[j]] in result:
result.append([num[i],num[k],num[j]])
while num[j] == num[j - 1] and j > k:
j -= 1
self.rec(num, i + 1,k, j - 1,result,False)
else:
tmpRe = self.binary(num, -num[j] - num[k] ,i,k )
if tmpRe == -1:

while num[j] == num[j + 1] and j > k:
j -= 1
j -= 1
self.rec(num, i,k, j,result, False)
else:
i = tmpRe
if not [num[i],num[k],num[j]] in result:
result.append([num[i],num[k],num[j]])
while num[i] == num[i + 1] and i < k:
i += 1
self.rec(num, i + 1,k, j,result,True)

def binary(self, a,key,lo,hi):

if hi < lo:
return -1
mid = lo + (hi - lo) / 2
if hi == lo:
if key == a[lo]:
return lo
else:
return -1
if key > a[mid]:
return self.binary(a,key,mid + 1, hi)
elif key < a[mid]:
return self.binary(a,key,lo,mid)
else:
return mid
``````

using time.clock(), it only took ~7ms with the TLE test case. Any suggestions?

• ``````vector<vector<int> > threeSum(vector<int> &num) {
sort(num.begin(), num.end());
int size = num.size();
vector<vector<int> > result;
set<vector<int> > rset;
for (int i = 0; i < size - 2; i++) {
int l = i + 1, r = size - 1;
while (l < r) {
int sum = num[i] + num[l] + num[r];
if (sum > 0)
r--;
else if (sum < 0)
l++;
else {
vector<int> s;
s.push_back(num[i]);
s.push_back(num[l]);
s.push_back(num[r]);
rset.insert(s);
l++; r--;
}
}
}
for (auto it = rset.begin(); it != rset.end(); it++)
result.push_back(*it);
return result;
}
``````

Mine, runs at ~15ms on local computer with the TLE case.

Not quite sure how to improve it to pass the online judge.

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