15. 3Sum

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.

Notice that the solution set must not contain duplicate triplets.

My Answer 1: Time Limit Exceeded (315 / 318 test cases passed.)

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        if len(nums) < 3:
            return []
        
        nums.sort()
        result = []
        
        i = 0
        j = 1
        while i != len(nums)-2:
            if j == len(nums)-1:
                i += 1
                j = i+1
            three = [nums[i]]
            three.append(nums[j])
            for k in range(j+1, len(nums)):
                if sum(three) + nums[k] == 0:
                    three.append(nums[k])
                    if three not in result:
                        result.append(three)
                    break
            j += 1
        
        return result

nums 를 sort 해주고 시작 => 중복된 값을 제외하기 편함
i 는 첫번째 값, j 는 두번째 값, k 는 세번째 값을 의미하고 세가지를 더한 값이 0 이고 result 에 같은 값이 없으면 넣어준다

하지만 ~~ 타임리밋

Solution 1: Runtime: 2408 ms - 22.96% / Memory Usage: 17.6 MB - 37.06%

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        length = len(nums)
        result = set()
        for i in range(length-2):
            left = i+1
            right = length-1
            while left < right:
                sum_value = nums[i]+nums[left]+nums[right]
                if sum_value == 0:
                    result.add((nums[i],nums[left],nums[right]))
                    left += 1
                    right -= 1
                elif sum_value < 0:
                    left +=1
                else:
                    right -= 1
        return result

O(n^2) 방식...
left 랑 right 를 이용한다
sum_value == 0 이면 result 에 넣어줌
sum_value < 0 이면 left 를 움직여서 합을 키운다.
그 외엔 right 를 줄여가면서 합을 줄인다.

while left < right: 부분 부터는 2sum 의 target 이 0 인거나 마찬가지..