문제
정답
오답
예상했지만, Brute force로 하면 TLE가 나온다.
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
nums = sorted(nums)
result = []
for ii in range(len(nums)):
if ii > 0 and nums[ii] == nums[ii - 1]:
continue
for jj in range(ii + 1, len(nums)):
if jj > ii + 1 and nums[jj] == nums[jj - 1]:
continue
for kk in range(jj + 1, len(nums)):
if kk > jj + 1 and nums[kk] == nums[kk - 1]:
continue
res = [nums[ii], nums[jj], nums[kk]]
if sum(res) == 0 and res not in result:
result.append(res)
break
return result
쓰리 포인터 구현
가장 왼쪽 숫자를 left
로 놓고, 나머지 숫자 내에서 투 포인터로 합을 계산하는 방식이다.
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
nums = sorted(nums)
result = []
for left in range(len(nums) - 2):
if left > 0 and nums[left] == nums[left - 1]:
continue
mid = left + 1
right = len(nums) - 1
while mid < right:
res = [nums[left], nums[mid], nums[right]]
res_sum = sum(res)
if res_sum < 0:
mid += 1
elif res_sum == 0:
result.append(res)
while mid < right and nums[mid] == nums[mid + 1]:
mid += 1
while mid < right and nums[right] == nums[right - 1]:
right -= 1
mid += 1
right -= 1
else:
right -= 1
return result