Quick python solution


  • 2
    C

    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]:
            			duplicates.add(n)
            		else:
    	        		hashsets[0].add(n)
            	else:
            		if n in hashsets[1]:
            			duplicates.add(n)
            		else:
    	        		hashsets[1].add(n)
            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

  • 0
    M

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


  • 0
    V

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


Log in to reply
 

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