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
Straight forward Python AC O(n^2) solution with decent explanation


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[i1]: # avoid duplication continue j = i + 1 k = len(nums)  1 while j < k: if j > i + 1 and nums[j] == nums[j1]: # 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
This makes a 232ms answer

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

@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.

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[idx1]: continue path = {} vist = set() for i in xrange(idx+1,len(nums)): if nums[i] not in path: path[tgtnums[i]] = nums[i] elif nums[i] in path and nums[i] not in vist: solution.append([tgt,path[nums[i]],nums[i]]) vist.add(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? Thetgt  nums[i]
bit has me thrown.How does
nums[i]
's presence as a key inpath
and nonpresence as a set value invist
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.