[LEET CODE] 15. 3Sum ( 투 포인터 활용)

# Problem

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero. Notice that the solution set must not contain duplicate triplets. Constraints: 0 <= nums.length <= 3000 -105 <= nums[i] <= 105

# My Solution 1

브루트포스 - Time Limit Exceeded

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        if len(nums)<3:
            return []
        answer=[]
        for a in range(len(nums)):
            for b in range(a+1,len(nums)):
                for c in range(b+1,len(nums)):
                    if nums[a]+nums[b]+nums[c]==0:
                        if sorted([nums[a],nums[b],nums[c]]) in answer:
                            continue
                        answer.append(sorted([nums[a],nums[b],nums[c]]))
        return answer

 

# My Solution 2 - 투 포인터 활용

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        if len(nums)<3:
            return []
        answer=[]
        nums.sort()
        for a in range(len(nums)-2):
            if a>0 and nums[a]==nums[a-1]:
                continue
            left = a+1
            right = len(nums)-1
            while left<right:
                if nums[left]+nums[right]>-nums[a]: # 값을 감소시켜야함
                    right-=1
                    
                elif nums[left]+nums[right]==-nums[a]: # 정답
                    if [nums[a],nums[left],nums[right]] not in answer: # 숫자가 중복될 수도 있으니
                        answer.append([nums[a],nums[left],nums[right]])
                    left+=1
                    right-=1
                else: # nums[left]+nums[right]<-nums[a]일 때 ,값을 증가시켜야 함
                    left+=1
                    
        return answer

 

 

# Solution 1 - 브루트 포스로 계산

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

 

# Solution 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: # 숫자를 증가시켜야함
                    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

---

# 투포인터

시작점과 끝점 두 지점을 기준으로 하는 문제 풀이 전략

배열이 정렬되어 있을 때 유용