[LeetCode] 15. 세 수의 합(3Sum)

배열을 입력받아 합으로 0을 만들 수 있는 3개의 엘리먼트를 출력하라.

 

Input: nums = [-1,0,1,2,-1,-4]

Output: [[-1,-1,2], [-1,0,1]]

 

 

1. 내가 직접 푼 코드

 

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums_list = []
        for i in range(len(nums) - 2):
            for j in range(i + 1, len(nums) - 1):
                for k in range(j + 1, len(nums)):
                    if nums[i] + nums[j] + nums[k] == 0 :
                        v = sorted([nums[i], nums[j], nums[k]])
                        if v not in nums_list:
                            nums_list.append(v)
        return nums_list

 

해설:

 

단순하게 for문 3개를 겹쳐서

(이것만은 하고 싶지 않았다..!)

3개의 합이 0이 되는 리스트를 뽑는다.

하지만 중복이 있어 정렬을 한 후에 nums_list에 없는 것만 받아들였다.

하지만 이 코드는 런타임 에러가 발생한다 ㅠㅠ

왜인지는 말 안 해도 알지?

 

 

for문이 3개인 것 같아서 for문을 2개로 하고

(i와 j까지만 하고)

if -nums [i] -nums [j] in nums [j+1:]

이런 식으로 만들어 봤는데 역시나 런타임 에러...

 

 

 

 

 

** 깔끔한 답안 **

 

2. 투 포인터로 합 계산

 

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:
                sum = nums[i] + nums[left] + nums[right]
                if sum < 0:
                    left += 1
                elif sum > 0:
                    right -= 1
                else:
                    result.append([nums[i], nums[left], nums[right]])
 
                    while left < right and nums[left] == nums[left + 1]:
                        left += 1
                    while left < right and nums[right] == nums[right - 1]:
                        right -= 1
                    left += 1
                    right -= 1
 
        return result

 

해설 :

 

i를 축으로 하고 중복된 값일 경우 건너뛰도록 한다.

그리고 i+1과 len(nums)-1을 포인터로 하고 sum을 계산.

만약 sum이 음수라면 left를 한 칸 나아가게 하고

sum이 양수라면 right에 -1을 더하여 sum이 0이 되는 방향으로 나아간다(천재임?).

 

그 후 sum=0을 찾았으면 다음 left와 다음 right가 중복되면 result가 중복되니까

left와 right를 중복된 값이 끝날 때까지 보내준다.

 

 

 

 

 

 

출처 : 파이썬 알고리즘 인터뷰 (글 : 박상길 그림 : 정진호) [책만]