LeetCode 15. 3Sum

by

In the previous post, we discussed the Two Sum problem. Please check it out below:
LeetCode 1. Two Sum

You can use either a two-pointer approach or a hashmap for this. Let’s try to reuse the Two Sum solution!

Table of Contents

Approach

Throughout the iteration, we can simply look for a pair of numbers that sum up to the complement of the current number.

Code

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        answer_set = set()

        def twoSum(src, target):
            h_set = set()
            twosum_res = []

            for i in range(src, n):
                if target – nums[i] in h_set:
                    twosum_res.append([nums[i], target-nums[i]])
                else:
                    h_set.add(nums[i])

            return twosum_res
       
        for i in range(n):
            res = twoSum(i+1, -nums[i])

            if res:
                for tok in res:
                    tok.append(nums[i])
                    answer_set.add(tuple(sorted(tok)))

        return [list(x) for x in answer_set]

Complexity

Time Complexity: O(N^2)
Space Complexity: O(N)


The code is accepted, but it seems to be slower than the other approaches I mentioned earlier. I suggest you also try them for fun!