[알고리즘] 세 수의 합

세 수의 합

내 풀이

3중 for 문을 이용한 풀이를 떠올렸으며, 이렇게 풀면 당연히 시간초과가 난다.

책 풀이

def threeSum(nums: List[int]) -> List[int]:
    results = []
    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:
            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

정렬을 해서 투포인터로 푼다.
왼쪽에서부터 하나씩 기준을 잡는다. 하나의 기준을 잡았으니 남은 오른쪽 부분에 대해 left와 right를 잡아서 해결해나간다. 단, 중복되는 요소들이 있을 수 있으므로 중복되는 것들은 건너뛰어 준다.