My O(n^2) Dictionary based Python solution (annotated with explanations). Concise and DRY!


  • 0
    J
    from collections import Counter
    
    class Solution(object):
        def threeSum(self, nums):
            def add_unique_combo(combo, seen): # Helper method to only add unique combinations
                sorted_combo = sorted(combo)
                if not str(sorted_combo) in seen:
                    results.append(sorted_combo)
                    seen[str(sorted_combo)] = True
    
            length, results, seen, counter = len(nums), [], {}, Counter(nums)
    
            # Handle special cases
            if length < 3: return []
            elif 0 in counter and counter[0] >= 3: add_unique_combo([0, 0, 0], seen)
    
            # Iterate through counter dictionary looking for unique combos
            for i in counter:
                for j in counter:
                    if i == j: continue # Current keys are the same, so skip
    
                    target = -(i + j) # Set target to look for to equal 0 sum
    
                    if (i == target or j == target):
                        if counter[target] > 1: add_unique_combo([i, j, target], seen)
                    elif target in counter:
                        add_unique_combo([i, j, target], seen)
    
            return results
    

  • 0
    J

    One weird thing I did encounter while writing this, hoping somebody can help me figure it out!

    When I write the following lines of code:

    if (i == target or j == target):
                        if counter[target] > 1: add_unique_combo([i, j, target], seen)
    

    like this:

    if (i == target or j == target) and counter[target] > 1: add_unique_combo([i, j, target], seen)
    

    It does not work. I need to have the inner if, otherwise I get incorrect results when trying to combine the statements with "and".

    Would love if anybody can help point out why that might be happening!


Log in to reply
 

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