9. 3Sum

리트코드

• 배열을 입력받아 합으로 0을 만들 수 있는 3개의 엘리먼트를 출력하라

1. 브루트 포스로 계산

• 앞뒤로 같은 값이 있을 경우, 이를 쉽게 처리하기 위해 먼저 sort() 함수를 사용해 정렬한다.

  • 정렬의 시간 복잡도는 O(nlogn)이며, 파이썬의 팀소트는 정렬 속도가 매우 빠르다.

  

• 그림에서 i,j,k 각각의 포인터가 계속 이동하면서 i + j + k = 0 을 찾아낸다.

• 이 브루트 포스 풀이에는 중복된 값이 있을 수 있으므로 continue로 건너뛰도록 처리한다.

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        
        results = []
        nums.sort()
        
        #브루트 포스 n^3 반복
        for i in range(len(nums)-2):
            #중복된 값 건너뛰기
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            for j in range(i+1, len(nums) - 1):
                if j > i + 1 and nums[j] ==nums[j-1]:
                    continue
                for k in range(j + 1, len(nums)):
                    if k > j + 1 and nums[k] == nums[k-1]:
                        continue
                    if nums[i] + nums[j] + nums[k] == 0:
                       results.append((nums[i], nums[j], nums[k]))
                    
        return results

• 이 풀이법은 시간이 너무 오래걸리기에 O(n^2)이내로 최적화를 진행해보자

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:
                    #0보다 작으면 값 키우기
                    left += 1
                elif sum > 0:
                    #0보다 크면 값 줄이기
                    right -= 1
                else:
                    #sum = 0인 경우이므로 정답 및 동일한 값의 경우 스킵처리
                    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