세 수의 합(Tree Sum)(틀림)
문제 Link
내 풀이
완전 탐색으로 문제를 풀었는데 내 코드는 왜 이렇게 더러운지 모르겠다. 처음에 3수를 사용해서 0이 나오는 모든 경우의 수(+, - 포함)을 구하다가 시간을 오래 소비했다. 제발 문제 좀 잘 읽자.
아래 코드는 시간 초과로 인해서 실패 난 코드이다.
첫 번째 두 수의 합이 0보다 큰 경우와 작은 경우를 나눠서 반복문을 좀 최적화 한다고 했는데 이것도 시간 초과가 났다.
class Solution:
def threeSum(self, nums: list[int]) -> list[list[int]]:
nums.sort()
i = 0
result = []
while i < len(nums) - 2 :
j = len(nums) - 1
while i < j :
cur_value = nums[i] + nums[j]
if cur_value >= 0 :
if cur_value < nums[i] :
break
k = i + 1
while k < j and nums[k] <= 0 :
if cur_value + nums[k] == 0 :
if [nums[i], nums[j], nums[k]] not in result :
result.append([nums[i], nums[j], nums[k]])
k += 1
if cur_value < 0 :
if -cur_value > nums[j] :
break
k = j - 1
while k > i and nums[k] >= 0 :
if cur_value + nums[k] == 0 :
if [nums[i], nums[j], nums[k]] not in result :
result.append([nums[i], nums[j], nums[k]])
k -= 1
j -= 1
i += 1
return result풀이 방법
1. 투 포인터 활용
class Solution:
def threeSum(self, nums: list[int]) -> list[list[int]]:
result = []
nums.sort()
for i in range(len(nums) - 2) :
# if i != 0 and nums[i] == nums[i - 1] :
# continue
left, right = i + 1, len(nums) - 1
while left < right :
value = nums[i] + nums[left] + nums[right]
if value < 0 :
left += 1
elif value > 0 :
right -= 1
else :
if [nums[i], nums[left], nums[right]] not in result :
result.append([nums[i], nums[left], nums[right]])
left += 1
right -= 1
return result