# Straight forward Python AC O(n^2) solution with decent explanation

• ``````class Solution:
# @param {integer[]} nums
# @return {integer[][]}
def threeSum(self, nums):
if len(nums) <3: # deal with special input
return []
elif len(nums) == 3:
if sum(nums) == 0:
return [sorted(nums)]

nums = sorted(nums) # sorted, O(nlgn)
ans = []

for i in range(len(nums) -2):
j = i+1
k = len(nums) -1 # hence i < j < k

while j<k: # if not cross line
temp_sum = nums[i] + nums[j] + nums[k]
if temp_sum == 0:
ans.append((nums[i], nums[j], nums[k]))

if temp_sum > 0: # which means we need smaller sum, move k backward, remember we sort the array
k -= 1
else:
j += 1

return list(set(tuple(ans))) # I bet this is not the best way to eliminate duplicate solutions``````

• Thank you so much!
I've been trying to solve the simplification problem with methods like list(set(ans)), which makes error. Now I get it!

------updated-----
well,I found a quicker way to avoid duplication:

``````def threeSum(self, nums):
if len(nums) <3:
return []
elif len(nums) == 3:
if sum(nums) == 0:
return [sorted(nums)]
nums.sort()
res = []
for i in list(range(len(nums)-2)):
if i > 0 and nums[i] == nums[i-1]: # avoid duplication
continue
j = i + 1
k = len(nums) - 1
while j < k:
if j > i + 1 and nums[j] == nums[j-1]: # avoid duplication
j += 1
continue
if k < len(nums) - 1 and nums[k] == nums[k+1]: # avoid duplication
k -= 1
continue
if nums[i] + nums[j] + nums[k] == 0:
res.append([nums[i],nums[j],nums[k]])
if nums[i] + nums[j] + nums[k] < 0:
j += 1
else:
k -= 1
return res
``````

• why do you need `list` in
`for i in list(range(len(nums)-2)):` ?

• @carterbao

slightly simpler and faster solution 170 ms

One possible optimization is to check this, then break earlier.

``````if nums[i] + nums[j] + nums[j + 1] > 0:
return res

class Solution(object):
def threeSum(self, nums):
nums.sort()
res = []
for i in range(len(nums) - 2):
j = i + 1
# small optimization
if nums[i] + nums[j] + nums[j + 1] > 0:
return res
k = len(nums) - 1
if i > 0 and nums[i] == nums[i - 1]:
continue
while j < k:
if j > i + 1 and nums[j] == nums[j - 1]:
j += 1
continue
total = nums[i] + nums[j] + nums[k]
if total > 0:
k -= 1
else:
if total == 0:
res.append([nums[i], nums[j], nums[k]])
j += 1
return res
``````

• Time limit exceeded.

• @carterbao
why do you use if...if.. else rather than if...elif...else? is the former more efficient?
I just a begginer and do a little change on your code using the latter again but time limit exceeded.

• if you encountered time limit error, you can add below code to the beginning of the loop of i

``````            if i != 0 and nums[i]==nums[i-1]:
continue

``````

• A generalization solution using 2Sum idea,

``````def three_sum(nums):
nums.sort()
solution = []
for idx,tgt in enumerate(nums):
if idx>0 and nums[idx] == nums[idx-1]:
continue
path = {}
vist = set()
for i in xrange(idx+1,len(nums)):
if nums[i] not in path:
path[-tgt-nums[i]] = nums[i]
elif nums[i] in path and nums[i] not in vist:
solution.append([tgt,path[nums[i]],nums[i]])
return solution
``````

• @jianx
This is brilliant. So elegant. Could you explain the logic that brought you to use the dict and set to track? The `-tgt - nums[i]` bit has me thrown.

How does `nums[i]`'s presence as a key in `path` and non-presence as a set value in `vist` determine that this iteration's sum == 0?

• @stueygk The dictionary is used for 2Sum where its key is the target value and value is current value. Once it finds the target value, you are done.

The vist set is to avoid duplicates. Examples like [-4, -1, -1, 0, 1, 2], the second -1 wouldn't show up in the answer once it has been visited and already is an answer.

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