[리트코드] 15. 3Sum - python

15. 3Sum

문제

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

제한사항

• 0 <= nums.length <= 3000
• -105 <= nums[i] <= 105

풀이

정렬한다.

3 포인터를 둔다.

0 - a = b+c 인 값을 찾는다. (값이 여러개일 수 있다.)

a를 이동시키면서 범위를 좁힌다.

만약 a가 target보다 크다면 종료한다.

class Solution:
    
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        answer = []
        
        for i, v in enumerate(nums):
            if v > 0:
                break
            left = i + 1
            right = len(nums) - 1
            
            while left < right:
                if nums[left] + nums[right] < -v:
                    left += 1
                elif nums[left] + nums[right] > -v:
                    right -= 1
                else:
                    if [v, nums[left], nums[right]] not in answer:
                        answer.append([v, nums[left], nums[right]])
                    left += 1
                    right -= 1
            
        
        return answer

개선

세 합을 기준으로 이분 탐색한다. 중복을 방지하기 위해서 if문 사용해 가지치기를 한다.

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        answer = []
        
        for i in range(len(nums) - 2):
            if i > 0 and nums[i] == nums[i - 1]: # 이미 체크한 값이면 패스
                continue
            l, r = i + 1, len(nums) - 1
            
            while l < r:
                s = nums[i] + nums[l] + nums[r]
                if s < 0:
                    l += 1
                elif s > 0:
                    r-= 1
                else:
                    answer.append((nums[i], nums[l], nums[r]))
                    while l < r and nums[l] == nums[l + 1]: # 중복 제거
                        l += 1
                    while l < r and nums[r] == nums[r - 1]: # 중복 제거
                        r -= 1
                    l += 1
                    r -= 1
        
        return answer