In an set of integers, find three elements summing to zero (3-sum, leetcode variant)

Question

I use a dummy solution to solve the leetcode 3Sum problem.

I employ the set data type to handle duplicates, then transform back to list.

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:

The solution set must not contain duplicate triplets.

Example:

Given array nums = [-1, 0, 1, 2, -1, -4],

A solution set is:

[
  [-1, 0, 1],
  [-1, -1, 2]
]

My codes:

from typing import List
import logging
import unittest
import random
from collections import defaultdict,Counter

##logging.disable(level=#logging.CRITICAL)
##logging.basicConfig(level=#logging.DEBUG, format="%(levelname)s %(message)s")

    class Solution:
        def threeSum(self, nums, target: int=0) -> List[List[int]]:
            """
            :type nums: List[int]
            :type target: int 
            """
            if len(nums) < 3: return []

            triplets = []
            if target == [0, 0, 0]: 
                triplets.append([0, 0, 0])
                return triplets # finish fast 

            lookup = {nums[i]:i for i in range(len(nums))} #overwrite from the high
            if len(lookup) == 1:#assert one identical element 
                keys = [k for k in lookup.keys()]
                if keys[0] != 0: 
                    return []
                else:
                    triplets.append([0,0,0])
                    return triplets



            triplets_set = set()

            for i in range(len(nums)):
                num_1 = nums[i]
                sub_target = target - num_1
                # #logging.debug(f"level_1_lookup: {lookup}")

                for j in range(i+1, len(nums)):
                    num_2 = nums[j]
                    num_3 = sub_target - num_2              
                    k = lookup.get(num_3) #             
                    if k not in {None, i, j}: #don't reproduce itself  
                        result = [num_1, num_2, num_3]
                        result.sort()
                        result = tuple(result)
                        triplets_set.add(result)

            triplets = [list(t) for t in triplets_set]
            return triplets 

My solution gets this result:

Your runtime beats 28.86 % of python3 submissions.

Could anyone please give hints to improve?

Answer 1

Multi-part answer: [0) these preliminaries] 1) review of code presented 2) hints for improvement excluding personal, from programming over python and accepting a programming challenge to k-sum and leetcode 3Sum.

One general principle to follow is do as expected, in programming, it has been formulated in many guises, including Principle of Least Surprise. Every other route leaves you under pressure to justify, at risk of being misunderstood.

In coding, document, in the program source code:
What is "everything" there for?

Such rules often have been gathered into guide lines, for Python, follow the Style Guide for Python Code.

---

• Instead of a docstring, your module starts with imports - most of them unused.
• If your code mentioned leetcode, the presentation of a class Solution with just one function definition wouldn't beg justification.
• the definition of threeSum() shows (a cute addition of target&default and) a curious mix of leetcode's templates for Python 2&3, lacking a proper docstring
• comparing "the int" target to the list literal [0, 0, 0] is dangerous given Python's zeal to allow operations: do you know by heart when that evaluates to True?
  (Do you expect most every reader of your code to?)
  (Belatedly, it occurred to me that you may have intended to compare nums to [0, 0, 0] - bogus if target != 0)
• verbosity - you can denote a tuple containing a single literal list like ([v, v, v],)
• 2nd early out:
  with only one key→value in the dict, there's no need to access it:
  every key will equal nums[0]
  You need to check for 3*nums[0] != target
• naming (Not your fault: Solution and threeSum are substandard.
  nums/_1-3 don't feel bad enough to change):
  - target, triplets, sub_target: right on!
  - given Python's "duck typing", I'd stick with triplets (, never introducing triplets_set)
  - lookup is a horrible name → value_to_index (or, in a suitably small context, just index)
  (- there's one thing wrong with k: it gets in the way when extending three_sum() to k_sum()…)
• pythonic or not (or exploiting library functions, rather?):
  value_to_index = { value: index for index, value in enumerate(nums) }
  (same for for i, num_1 in enumerate(nums), for j, num_2 in enumerate(nums[i+1:], i+1))
• commenting
  - you did comment, and I find half of the comments helpful
  - I don't get #overwrite from the high (that may just be me)
  - #don't reproduce itself: probably use any element/index once, at most rather than don't repeat an element/index
  - you did not comment the outer for loop, arguably the most profitable place:
  how is what the execution constructs a solution?:
  for each value, value_to_index keeps just the last index: how does this not prevent any valid triple to show up in the solution?
• checking k: nice!
  (I'd go for in (None, i, j))

• you don't provide a "tinker harness"

  if __name__ == '__main__':
      object_disoriented = Solution()
      print(object_disoriented.threeSum([-1, 0, 1, 2, -1, -4]))
      print(object_disoriented.threeSum([1, 1, 1], 3))
  

---

(Something else to follow is make (judicious) use of every help you can: if you use an IDE supporting Python, chances are it can help you with PEP8.) (Running low on steam, this part will start more frugal than expected.)

Real Programming is the creation of a language that simplifies the solution of the problem at hand.

With Python providing most mechanisms needed in programming challenges, that leaves:

• Code readably.
• Create elements easy to use correctly.

I bickered you some about having a consistent problem description.
This is another place where Test First shines:
As long as you find yourself not knowing what to test, you are not in a position to implement anything, yet. (Inconsistencies in specification tend to stand out in test design & implementation.)

Programming challenges à la leetcode.com typically build on simpler challenges - you met 2sum, which puts you in a favourable position to tackle 3sum.
The performance part of these challenges is about not doing things over, not discarding knowledge more often than about algebraic insight.

The generic solution to 2sum is to take values and find the complement (1sum?).
The extension to k-sum is to split k into smaller numbers.

Ways to have information about the order of a set or sequence (say, elements) of instances of a type with ordering reusable is to have them ordered (ordered = sorted(elements)) or sorted (histogram = Counter(elements)).
For 2sum, you could search for target/2 and work inside-out.
For 3sum, one value will be no greater, another no smaller than both others. The third one will not "lie outside" the former two.