Solution to 3Sum problem on LeetCode using hash table

Question

The problem of 3sum is described as:

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.

Here is my code. Am I right to say its complexity is O(N²), and how can I further optimize my code? I am using a hash table:

class Solution(object): def threeSum(self, nums): """ :type nums: List[int] :rtype: List[List[int]] """ dct = {} trip = {} triplet = [] nums_len = len(nums) for i in range(nums_len - 1): for j in range(i + 1, nums_len): key = nums[i] + nums[j] if key in dct: if (i in dct[key]): continue dct[key] = dct[key] + [i, j] # If exists, append more in a bucket else: dct[key] = [i, j] for k in range(nums_len): supplement = -1*nums[k] # nums[k] = - (nums[i] + num[j]) if supplement in dct: entry = dct[supplement] #look on the dict entry_len = len(entry) entry_num = entry_len//2 for m in range(entry_num): pair = [entry[m*2], entry[m*2+1]] if (k not in pair): candidate = [nums[entry[m*2]], nums[entry[m*2+1]], nums[k]] candidate.sort() key = str(candidate[0]) + str(candidate[1]) + str(candidate[2]) if (key not in trip): trip[key] = True triplet.append(candidate) return triplet 

Answer 1

I don't use LeetCode, but I assume the site might constrain you to declaring a class and using that function name and input parameter name in order to submit your code.

I'll review the code under the assumption that you would use it for general consumption, not just limited to this specific programming-challenge site. The review is mainly for style and is unlikely to improve your performance.

Naming

It is common to pluralize array variable names. For example, triplet would be triplets.

dct is not a very meaningful name.

Simpler

Lines like this:

dct[key] = dct[key] + [i, j] 

are simpler using the special assignment operators:

dct[key] += [i, j] 

There is no need for the intermediate variable entry_len:

entry_len = len(entry) entry_num = entry_len//2 

It is simpler as:

entry_num = len(entry) // 2 

Comments

The following comment should be deleted since it adds clutter:

supplement = -1*nums[k] # nums[k] = - (nums[i] + num[j]) 

It looks like commented-out code.

Cleaner

The code is cleaner when you omit the parentheses in an if statement. for example:

if (i in dct[key]): 

is cleaner as:

if i in dct[key]: 

DRY

This line:

key = str(candidate[0]) + str(candidate[1]) + str(candidate[2]) 

is more scalable with a loop:

for i in range(3): key += str(candidate[i])