리트 코드 세수의 합

리트 코드 세수의 합

리트 코드 세수의 합

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

• 입력

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

• 출력

[
[-1, 0, 1],
[-1, -1, 2],
]

이 문제의 경우 투 포인터를 이용해 풀 수 있다. 하지만 투 포인터로 풀려면 숫자가 정렬되있어야 한다.

nums.sort()로 우선 숫자를 정렬해주고 for문을 이용해 nums[i]부터 하나씩 뽑는다. 그리고 i+1과 len(num)-1을 각각 left, right 포인터로 정한다.

그 후 hap이라는 변수에 nums[i] + nums[left] + nums[right]을 넣어주고 이 값이 0보다 크다면 right-=1 0보다 작다면 left+=1 0이라면 result에 append 하는 방식으로 알고리즘을 구현하였다.

코드를 보게되면

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:
                hap = nums[i] + nums[left] + nums[right]
                if hap>0:
                    right -=1
                elif hap<0:
                    left += 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

위와 같다. result는 빈 리스트 nums는 투 포인터를 사용하기 위해 정렬해주었다. 그 후 i값 외에 포인터 두개를 사용하기 때문에 range(len(nums)-2)로 주었다.

여기서 중복 처리가 중요한데 if i>0 and nums[i]==nums[i-1]:
continue 여기서 i값이 직전 값과 같다면 시간을 줄이기 위해 넘긴다.

그 후 while문 안에 left<right 조건을 주고 투 포인터를 구현한다.

else: 부분에 append 한 후 중복을 넘기는 처리를 해주었는데 이렇게 해준 후 left += 1 right -= 1을 해주어야 0을 찾은 후에 while문을 빠져나갈수 있다.

출처: 파이썬 알고리즘 인터뷰(박상길 지음)