[Leetcode][Python] 15. 3Sum

리트코드 / 파이썬 / 15. 3Sum

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

3Sum - LeetCode

풀이 방법

 

1) pivoting 할 수 있도록 input list를 오름차순으로 정렬한다.

2) 아래와 같이 초기화하고, 다음과 같은 조건이 오는 경우 left/right 를 업데이트한다. (단, left, right은 list의 index)

. 초기화 : now = 0, left = now + 1, right = len(nums) - 1

. 업데이트 조건 : i) sum(nums[now] + nums[left] + nums[right])이 0인 경우, 결과 list에 추가
                          ii) sum이 0보다 작은 경우, left에 +1을 더해준다.
                          iii) sum이 0보다 큰 경우, right에 -1를 더해준다. ** list가 오름차순으로 정렬돼있다.

. 주의사항 : 중복은 피해야 한다. (결과 list의 element)

 

복잡도는 list의 길이 만큼 for loop를 돌고, 그 안에서 left, right이 list의 길이 만큼 순회하므로 (중간에 left와 right이 만나면 탐색이 중단됨) O(N^2)가 된다.

 

소스 코드

class Solution(object):
    def threeSum(self, nums):
        """
        https://leetcode.com/problems/3sum/
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        res = list()
        nums = sorted(nums)

        for i in range(len(nums)):
            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:
                    res.append(sorted([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 res