Python Solution:

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        result = []
        #[-1,0,1,2,-1,-4]
        nums.sort() #O(nlogn) for sorting
        #[-4,-1,-1,0,1,2]
        for i in range(len(nums)):
            #i=0,1,2...
            #nums[i], smallest number in 3 numbers
            if nums[i] > 0:
                break
            if i == 0 or nums[i - 1] != nums[i]: #avoid duplicate num[i], nums[-1] crash
                self.twoSum(nums, i, result)
        return result
    
    def twoSum(self, nums: List[int], i: int, result: List[List[int]]):
        j = i + 1 #nums[j] ~ biggest number
        hashset = set()
        #Python set, duplicates not allowed. Hashset stores the selections for the 3rd number, medium number
        #hashset={}        
        
        while j < len(nums):
            #fix i and j
            complement = 0 -nums[i] - nums[j]

            if complement in hashset:
                result.append([nums[i], nums[j], complement])
                #avoid duplicates of nums[j]
                while j + 1 < len(nums) and nums[j] == nums[j + 1]:
                    j += 1
            hashset.add(nums[j])
            j += 1
    
        return result

 

Time Complexity: O(n^2) for two layer loop

Space Complexity: O(n) for hashset

Feeling tired? You can also try our free online no-installation required casual games: Here Please consider to follow my youtube channel to support me: