# Solution to 3Sum problem on Leetcode using HashTable

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(N2), and how can I further optimize my code? Here I am using HashTable:

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) +  str(candidate) + str(candidate)
if (key not in trip):
trip[key] = True
triplet.append(candidate)

return triplet

• Welcome to Code Review. Please add a language tag. – Heslacher Aug 7 '19 at 13:15
• You might get some inspiration from codereview.stackexchange.com/q/213328/35991. – Martin R Aug 7 '19 at 13:25
• It is very difficult to optimize when we don't know what language the code is. – pacmaninbw Aug 7 '19 at 13:53
• Is nums a unique list? – C.Nivs Aug 7 '19 at 17:36
• I am so sorry, the code is Python2, and nums is not a unique list. Should I write some more comments in code to clarify my idea? – Giang Nguyễn Aug 8 '19 at 1:41