1. 문제

문제링크 : https://leetcode.com/problems/3sum

2. 풀이

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

        for i in range(len(nums) - 2):
            # 중복된 값 건너뛰기
            if i > 0 and nums[i] == nums[i - 1]:
                continue

            # 간격을 좁혀 sum 계산
            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:
                    results.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 results

처음엔 세 개의 반복문을 사용하는 브루트포스 방식으로 풀었는데 시간초과가 났다. 시간 복잡도를 $O(n^3)$에서 $O(n^2)$ 정도로 낮춰야 한다. 이 풀이에선 투 포인터를 활용하여 시간 복잡도를 낮춘다. 전체 코드를 처음부터 살펴보면, 먼저 중복된 값을 쉽게 찾을 수 있도록 nums를 정렬한다. 첫 번째 for문에서 중복된 값이 존재하는지 확인한 후 투 포인터인 left, right 값을 설정한다. while문에서 sum을 먼저 계산하고 값이 0보다 큰지 작은지에 따라 left 또는 right를 이동시킨다. 만약 sum이 0이면 results에 현재 i, left, right에 해당하는 nums의 원소들을 패킹하여 추가한다. 추가 후엔 left, right가 중복된 값을 가리키지 않도록 이동시킨 다음에 left, right를 1씩 이동시킨다. nums를 정렬할 때 사용되는 팀소트는 시간 복잡도가 $O(n\log n)$이고 투 포인터를 사용한 while문의 시간 복잡도가 $O(n)$이므로 for문의 시간 복잡도는 $O(n^2)$가 된다. 따라서 전체 시간 복잡도는 $O(n^2)$가 된다.