세 수의 합 문제

 배열을 입력 받아서 합으로 0을 만들 수 있는 3개의 원소를 출력하라.

세 수의 합이 0 이 되는 원소를 찾아 

풀이 1) 브루트 포스 

for 문을 3개 중첩하여 모든 가능한 3 원소 쌍을 만들어서 0이 되는지 비교한다. 실제 리트코드에서는 타임 아웃 된다.

for 문 사이에 if 문이 의미하는 것은 이미 i, j, k 조합이 중복됨을 방지하기 위함이다. 앞에서 이미 한 것이면 생략하는 것이다.! 중복을 쉽게 피하기 위해서 nums.sort() 로 정렬을 미리 해주었다.

    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
                
            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

 

풀이 2) 투 포인터로 합 계산.

 

브루트 포스 방법이 $n^{3}$ 계산량이 었는데 투 포인터로 하면 계산량이 $n^{2}$ 계산량으로 준다.

먼저 풀이 1) 처럼 sort 를 해주고, i 를 잡고 나서 i+1 지점이 left, 마지막 지점이 right 로 잡아서 셋이 더해가면서 sum 이 0 보다 크면 right 를 왼쪽으로 한 칸씩 보내고, 0 보다 작으면 left 를 오른쪽으로 한 칸씩 보내서 점점 0 에 가까워 지게 한다.

만약 0을 발견했다면 중복을 피하기 위해 left 와 right 를 확인해서 중복을 벗어나게 해준다.

    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
                
            # 간격을 좁혀가며 합 계산
            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:
                    # 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