class Solution:
# @param {integer[]} nums
# @return {integer[][]}
def threeSum(self, nums):
n = len(nums)
h = {}
rlt = []
for i in range(n):
h[nums[i]] = i
for i in range(n):
for j in range(n):
if i != j:
x = (nums[i]+nums[j])
if x in h and h[x] != i and h[x] != j:
t = tuple(sorted([nums[i],nums[j],x]))
if t not in rlt: rlt.append(t)
return rlt
Python O(n^2) TLE why?


The reason I think is that you didnot avoid duplicates in your process, yes, the result of your code maybe is correct, and the time complexity is O(n*n) the same as others, but the OJ for this question is a little bit strict, such as if the list is 1, 0, 0, 1, 1, 1, 1, 1, 1, after you checking the first 1, you can move the index forward without checking the sum, because they are duplicates. Here is a method to avoid duplicates, just for reference.
def threeSum(self, nums): nums.sort() res, leng = [], len(nums) for i in xrange(leng2): if i == 0 or nums[i] != nums[i1]: l, r = i+1, leng1 while l < r: s = nums[i] + nums[l] + nums[r] if s == 0: res.append((nums[i], nums[l], nums[r])) while l < r and nums[l] == nums[l+1]: l += 1 while r > l and nums[r] == nums[r1]: r = 1 l += 1; r = 1 elif s > 0: r = 1 else: l += 1 return res