[LeetCode | Python] 15. 3Sum

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

 

풀이 1: 브루트 포스 - 시간 초과

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        res = set()
        nums.sort()
        for i in range(len(nums)):
            for j in range(i+1, len(nums)):
                for k in range(j+1, len(nums)):
                    if nums[i] + nums[j] + nums[k] == 0:
                        res.add((nums[i], nums[j], nums[k]))
        return [list(i) for i in res]

res를 list로 만들면 중복된 것을 추가하지 않기 위해 in으로 또 검사해야 하므로 시간 복잡도가 증가한다.

그래서 res를 set()으로 만들고, 튜플 형태로 추가한다.

이에 따라 시간 복잡도는 O(n^3)이고, 리트코드에서는 시간 초과가 나서 통과하지 못하였다.

 

res.add([nums[i], nums[j], nums[k]])는 Runtime Error (TypeError: unhashable type: 'list') 가 난다는 것에 주의하자.

Python의 set은 내부적으로 해시 값을 이용해 중복 여부를 확인하므로, 해시 가능한 데이터 타입만 저장할 수 있다.

mutable (변경가능)한 값은 해시가 불가능하다. 따라서 튜플로 추가해주어야 한다.

 

 

풀이 2: Two Pointers

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        res = []
        nums.sort()

        for i in range(len(nums)):
            if i > 0 and nums[i] == nums[i-1]:
                continue
            
            j = i + 1
            k = len(nums) - 1

            while j < k:
                total = nums[i] + nums[j] + nums[k]
                
                if total > 0:
                    k -= 1
                elif total < 0:
                    j += 1
                else:
                    res.append([nums[i], nums[j], nums[k]])
                    j += 1

                    while nums[j] == nums[j-1] and j < k:
                        j += 1
        return res

먼저 투포인터로 풀이하기 위해 nums 배열을 정렬한다. 

첫번째 숫자(i)를 기준으로 for문을 순회하고, 두번째(j) 세번째(k) 인덱스를 투포인터로 사용한다.

똑같은 숫자가 여러 개 나올 때 의미 없이 조건문에서 검사하는 것을 건너뛰기 위해

while nums[j] == nums[j-1] and j < k: 를 통해 검사하고 j를 건너뛰도록 한다.

 

nums.sort()에서 O(n log n)

for i in range(len(nums)) 에서 O(n)

while j < k: 에서 O(n)이므로

O(n log n) + O(n) * O(n)  = O(n^2)

총 시간복잡도는 O(n^2)이다.