15. 3Sum

문제

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.

The solution set must not contain duplicate triplets.

예시

Given array nums = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

풀이

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        res = []
        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 :
                summ = nums[i] + nums[left] + nums[right]
                if summ == 0 :
                    temp = [nums[i],nums[left],nums[right]]
                    if res and res[-1] == temp:
                        pass
                    else:
                        res.append(temp)
                if summ > 0 :
                    right -= 1
                else:
                    left += 1
        return res

문제에서 요구하는 것은 아주 간단하다. 주어진 input에서 합이 0이 되는 3개의 원소의 집합을 구하는 것이다. 하지만 합이 0이 되는 원소들의 조합과 input 안에 존재하는 중복 원소에 대한 처리가 있어야지 시간초과를 피할 수 있다.

3 원소의 합을 구하기 위해서 먼저 기준 원소를 정한 뒤에 기준 원소를 기준으로 다른 원소와의 합을 for문으로 한번씩 돌게 되면 된다. 처음에는 input 리스트를 정렬하게 되면 중복을 continue로 쉽게 처리해 줄 수 있고 다른 2개의 원소를 양 끝 포인트를 시작으로 한번씩 더해가면서 0을 만들어 주는 작업을 진행한다.

이 때, 한가지 중요한 점은 중복을 처리해준 기준 원소 이외에도 중복값이 있기 때문에 0을 만들어주는 똑같은 조합이 생성될 수 있다. 하지만 그 경우에도 결과가 저장되는 공간에서 마지막에만 해당될 수 있기 때문에 마지막과 비교해서 저장 유무를 결정해준다.

결과

313 / 313 test cases passed.
Status: Accepted
Runtime: 1124 ms
Memory Usage: 17.1 MB
Submitted: 4 minutes ago