[배열] 09 세 수의 합(3Sum)

<LeetCode 문제>

https://leetcode.com/problems/3sum/

3Sum - LeetCode

배열을 입력받아 합으로 0을 만들 수 있는 3개의 엘리먼트를 출력하는 문제입니다.

<풀이>

배열 길이의 최댓값이 3000이므로 브루트포스를 통한 O(N³)으로는 시간초과가 납니다.

따라서 배열을 정렬한 이후에 투 포인터를 이용해서 간격을 좁혀나가며 sum을 계산해 나가야 합니다.

sum이 0보다 작다면 left를 우측으로, 0보다 크다면 right를 좌측으로 이동합니다.

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        results=[]
        nums.sort() #정렬
        
        for i in range(len(nums)-2):
            left, right = i+1, len(nums)-1 #인덱스 i+1부터 끝까지
            
            while left < right: #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]])
                    left+=1
                    right-=1
        
        #중복제거
        new_results=[]
        for res in results:
            if res not in new_results:
                new_results.append(res)
                
        return new_results

 

중복제거를 탐색하는 과정에서 할 수도 있습니다.

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
            
            left, right = i+1, len(nums)-1 #인덱스 i+1부터 끝까지
            
            while left < right: #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

 

<학습내용>

1. 정렬후에 투 포인터를 통해 합을 구해나가는 과정

<학습이 필요한 내용>

1. 투 포인터 풀이에 익숙해지기

 

https://github.com/HoYoungChun/Algorithm_PS/blob/master/Python_Study/07_array/LC_15.py

GitHub - HoYoungChun/Algorithm_PS: Baekjoon Online Judge, Programmers, LeetCode problem solving by Python, C++