[Python] Leet Code 15. 3Sum

본 내용은 <파이썬 알고리즘 인터뷰>를 참고했습니다.

투 포인터 활용

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:

        output = []
        nums = sorted(nums)

        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:
                    output.append([nums[left], nums[right], nums[i]])

                    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 output

이 문제에서 배워야할 포인트

• 가장 먼저 해야할 것은 sort
• 문제를 보면 제일 먼저 떠오르는 3중 for문 브루트 포스 풀이 방법은 시간이 오래 걸린다. (O(n^3))
• 투 포인터의 합을 이용한 풀이법으로 시간을 줄일 수 있다.(O(n^2))
• 중복 리스트가 포함되면 안되므로, 정렬된 리스트의 앞뒤 원소가 같다면 건너뛴다.
• 특히 정답을 찾았을 때, 이후 중복 처리하는 부분 주의할 것.