[python] 15. 3sum

3Sum - LeetCode

3Sum - LeetCode

 

세 수의 합

입력받은 숫자 배열에서

세 수를 더하여 0이 되는 3수의 조합을 반환하는 문제 

 

풀이

 

브루트 포스 

 

모든 수를 조합하여 더하여 합이 0이 되는 조합을 찾으면 풀이할 수 있다. 

# 브루트 포스
# Time Limit Exceeded

from typing import List
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:

        result = []
        nums.sort()
        # 가능한 조합을 모두 찾자
        for i in range(len(nums)-2):
            for j in range(i + 1, len(nums)-1):
                for k in range(j + 1, len(nums)):
                	# 세 수의 합이 0이고, 중복된 배열이 아니면 
                    if(nums[i] + nums[j] + nums[k] == 0 and [nums[i], nums[j], nums[k]] not in result):
                        result.append([nums[i], nums[j], nums[k]])
        return result

그러나 브루트 포스로 풀이하게 되면 시간 복잡도가 O(n^3)이 되어 타임 아웃된다. 

 

투 포인터

 

i보다 큰 값들을 기준으로 left와 right로 포인터를 나누어 계산한다. 

 

포인터 이동 조건

sum < 0 이면 left += 1

sum > 0 이면 right -= 1

from typing import List
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        # 투포인터
        nums.sort()
        result = []

        for i in range(len(nums)-2):
            # 중복일 때
            if i > 0 and nums[i] == nums[i-1]:
                continue
            # 중복이 아닐 때 투포인터
            left = i+1
            right = len(nums)-1
            while left < right:
                sum = nums[i] + nums[left] + nums[right]
                if sum < 0:
                    left += 1
                elif sum > 0:
                    right -= 1
                else:
                    result.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 result

 

추가 개념 - 투 포인터 

 

여러가지 방식이 존재하지만 

시작점과 끝점, 왼쪽과 오른쪽을 두 지점에서 포인터를 좁혀가며 풀이하는 방식을 의미한다. 

 

배열이 정렬되어 있을 때 사용하기에 좋다.