[LeetCode] 3Sum | 투포인터 | 파이썬 알고리즘 인터뷰, 정답, 소스코드

박상길, 『파이썬 알고리즘 인터뷰』를 정리한 내용입니다.

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

3Sum - LeetCode

---

문제 요약

• 정수 배열이 주어질 때, 세수의 합이 0인 정수 리스트를 구하라
• 단, 정답에 중복이 존재해서는 안된다. 

---

핵심 개념

• 개념 자체는 매우 간단하나 시간초과를 피하기 위해서는 효율적으로 풀어야 한다. 
• 세 수의 합이 0이 되기 위해서는 모든 수가 0이거나 음수인 수가 존재해야 한다. 
• nums가 정렬되어 있으면 세수의 합의 크기를 예상할 수 있다.
  (왼쪽에 있으면 값이 작아지고 오른쪽에 있으면 값이 커짐)

---

알고리즘

---

소스코드

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

        nums.sort()

        for i in range(len(nums) - 2):
            if nums[i] > 0:
                break

            if i > 0 and nums[i] == nums[i-1]:
                continue

            left, right = i+1, len(nums)-1
            while left < right:
                three_sum = nums[i] + nums[left] + nums[right]

                if three_sum == 0:
                    answer.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
                elif three_sum < 0:
                    left += 1
                else:
                    right -= 1

        return answer