[leetcode-15] Three Sum

LeetCode-15

Match Three sum : Notice that the solution set must not contain duplicate triplets.

note : myAnswer

MyAnswer(Time Limit Exceeded) O(n^2)

        :::python

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        a = []
        nums.sort()
        for i, n in enumerate(nums):
            d = {}
            for j in range(i+1,len(nums)):
                complete = - (n + nums[j])
                if complete in d:
                    if sorted([n, nums[j], complete]) not in a:
                        a.append(sorted([n, nums[j], complete]))
                else:
                    d[nums[j]] = j
        return a

Result : 9669ms Memory: 19.4mb

Answer(Two Point Sum) base|left|right

        :::python

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        results = []
        nums.sort()
        for i in range(len(nums)-2):
            # skip duplicate number 
            if i > 0 and nums[i]==nums[i-1]:
                continue
            left, right = i+1, len(nums)-1
            while left < right:
                sum = nums[i] + nums[left] + nums[right]
                if sum < 0:
                    left+=1
                elif sum > 0:
                    right-=1
                else:
                    results.append([nums[i],nums[left],nums[right]])
                    while left < right and nums[left]==nums[left+1]:
                        left+=1
                    while left < right and nums[right]==nums[right-1]:
                        right-=1
                    left+=1
                    right-=1
        return results

Result : 1389ms Memory: 18.3mb