2
\$\begingroup\$

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

        return triplet
\$\endgroup\$
  • 2
    \$\begingroup\$ Welcome to Code Review. Please add a language tag. \$\endgroup\$ – Heslacher Aug 7 at 13:15
  • \$\begingroup\$ You might get some inspiration from codereview.stackexchange.com/q/213328/35991. \$\endgroup\$ – Martin R Aug 7 at 13:25
  • 1
    \$\begingroup\$ It is very difficult to optimize when we don't know what language the code is. \$\endgroup\$ – pacmaninbw Aug 7 at 13:53
  • \$\begingroup\$ Is nums a unique list? \$\endgroup\$ – C.Nivs Aug 7 at 17:36
  • \$\begingroup\$ 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? \$\endgroup\$ – Giang Nguyễn Aug 8 at 1:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.