I think the time complexity is O(n^2). Don't know why it got TLE even on not a super large input. [7,-1,14,-12,-8,7,2,-15,8,8,-8,-14,-4,-5,7,9,11,-4,-15,-6,1,-14,4,3,10,-5,2,1,6,11,2,-2,-5,-7,-6,2,-15,11,-6,8,-4,2,1,-1,4,-6,-15,1,5,-15,10,14,9,-8,-6,4,-6,11,12,-15,7,-1,-9,9,-1,0,-4,-1,-12,-2,14,-9,7,0,-3,-4,1,-2,12,14,-10,0,5,14,-1,14,3,8,10,-8,8,-5,-2,6,-11,12,13,-7,-12,8,6,-13,14,-2,-5,-11,1,3,-6]
I ran it on my own computer, the output is correct, so there is no infinite loop in the code. Any one else uses python and have similar issue?
Share my code here
def threeSum(self, num): length = len(num) if length < 3: return  num = self.sort(num) triplets =  for i in range(0, length-2): if i>=1 and num[i] == num[i-1]: continue j = i+1 k = length-1 while j<k: if j> i+1 and num[j] == num[j-1]: j = j+1 continue if k<length-1 and num[k] == num[k+1]: k = k-1 continue s = num[i] + num[j] + num[k] if s == 0: triplets.append([num[i], num[j], num[k]]) j = j+1 k = k-1 elif s>0: k = k-1 else: j = j+1 return triplets def sort(self, num): length = len(num) if length <= 1: return num middle = int((length-1)/2) left = self.sort(num[0:middle+1]) right = self.sort(num[middle+1:length]) new_num =  p1 = 0 p2 = 0 length1 = len(left) length2 = len(right) while p1<=length1-1 and p2<=length2-1: if left[p1] < right[p2]: new_num.append(left[p1]) p1 = p1+1 else: new_num.append(right[p2]) p2 = p2+1 if p1<= length1-1: new_num.extend(left[p1:length1]) elif p2 <= length2-1: new_num.extend(right[p2:length2]) return new_num
same problem with you. I also implement a O(n^2) and get a TLE with the same input. I also check this on my computer and the answer is correct. Have no idea why it could be.
I used the input data of TLE case for my submission to run it on my own computer and it cost only 14 ms. I think there must be something wrong with OJ (maybe the special judge is broken).
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.