# Quick python solution

• In order to speed things up, analyze the question a little bit. Notice that if a+b+c==0, then there are either 2 negatives, or 2 non-negatives, or three 0's (trivial case). So, if we divide num array to 2 parts, negative, and non-negative, then, we can separately search pairs in the negative part and in the non-negative part, and see if there is a corresponding value in the other part equal to the -sum of the pair. Because each of the parts are smaller than the whole array, the n^2 search time is significantly shortened in most cases. This turns out to be among the fastest python submissions.

``````class Solution:
# @return a list of lists of length 3, [[val1,val2,val3]]
def threeSum(self, num):
results=[]

hashsets=[set(),set()] # hashsets[0] for negative numbers, hashsets[0] for 0 and positive numbers
duplicates=set()	#record duplicate numbers, triplets and above should be counted as duplets, except in case of triplet 0's.
for n in num:
if n==0 and 0 in hashsets[1] and 0 in duplicates and len(results)==0:
results.append([0,0,0])
if n <0:
if n in hashsets[0]:
else:
else:
if n in hashsets[1]:
else:
sortedLists=[sorted(hashsets[0]),sorted(hashsets[1])]

for x in xrange(len(sortedLists[0])):
if sortedLists[0][x] in duplicates:
if -2*sortedLists[0][x] in hashsets[1]:
results.append([sortedLists[0][x],sortedLists[0][x],-2*sortedLists[0][x]])
for y in xrange(x+1,len(sortedLists[0])):
if -(sortedLists[0][x]+sortedLists[0][y]) in hashsets[1]:
results.append([sortedLists[0][x],sortedLists[0][y],-sortedLists[0][x]-sortedLists[0][y]])

for x in xrange(len(sortedLists[1])):
if sortedLists[1][x] in duplicates:
if -2*sortedLists[1][x] in hashsets[0]:
results.append([-2*sortedLists[1][x],sortedLists[1][x],sortedLists[1][x]])
for y in xrange(x+1,len(sortedLists[1])):
if -(sortedLists[1][x]+sortedLists[1][y]) in hashsets[0]:
results.append([-sortedLists[1][x]-sortedLists[1][y],sortedLists[1][x],sortedLists[1][y]])

return results``````

• Why the case can't be 1 negative, 1 non-negative and 1 zero?

• The case you mention here is belong to 2 non-negatives.

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