728x90
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)이다.
728x90
