[파이썬] 리트코드 15. 3Sum 풀이

https://leetcode.com/problems/3sum/

3Sum - LeetCode

n개의 숫자리스트가 주어졌을 때 세 수의 합이 0이 되는 세 수를 구해야 한다. 

이 문제를 투 포인터를 이용하여 풀었다. 반복문의 인덱스를 i로 두었을 때, 나머지 두 수를 포인터로 두고 이동시켜주며 0이 되는 케이스를 탐색했다.

 

1. 정렬해준다. 세 수의 인덱스를 출력하는 문제가 아니라 정렬을 해두는 것이 편리하다. 그리고 중복된 숫자가 있을 때 정리하기 쉽다 

2. 반복문을 설정한다. 포인터가 두 개 존재하므로, 범위를 -2해줘야 한다 

3. 왼쪽 포인터를 l, 오른쪽 포인터를 r로 설정한다. l은 i보다 한 칸 오른쪽에 있고, r은 가장 마지막 칸에 있다 

4. l가 r보다 커질 때까지 세 수의 합이 0이 되는 케이스를 찾는다 

    - 배열이 오름차순이므로, 합이 0보다 작다면 조금 더 오른쪽에 있는 수를 탐색해야 한다. 따라서 l += 1 

    - 합이 0보다 크다면 더 작은 수, 더 왼쪽에 있는 수를 탐색해야 한다. 따라서 r -= 1 

5. 세 수의 합이 0이 되는 경우 answer에 추가해준다. 중복된 숫자가 존재하면 두 번 탐색하지 않도록 포인터를 한 칸 더 이동시킨다 

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        answer = []
        nums.sort()
        for i in range(len(nums)-2):
            if i>0 and nums[i] == nums[i-1]:
                continue 
            l, r = i+1, len(nums)-1
            while l<r:
                sum = nums[i] + nums[l] + nums[r]
                if sum<0:
                    l += 1 
                elif sum>0:
                    r -= 1 
                else:
                    answer.append([nums[i],nums[l],nums[r]])
                    while l<r and nums[l] == nums[l+1]:
                        l += 1 
                    while l<r and nums[r] == nums[r-1]:
                        r -= 1 
                    l += 1
                    r -= 1
        return answer 

 

<참고>

https://g.co/kgs/dxyfp7

파이썬 알고리즘 인터뷰