Leetcode Python - 16. 3Sum Closest

Leetcode #16 - 3Sum Closest

이번에는 특정 챕터별로 문제들을 풀어보겠습니다. string을 집중적으로 풀어보겠습니다.

리트코드의 문제 16 ‘3Sum Closest’을 파이썬으로 풀어 보도록 하겠습니다.

포인트는 loop로 하나의 수를 기준을 잡은 뒤에 binary search를 이용하면 됩니다.

전체 코드는 아래와 같습니다.

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        if len(nums) == 3:
            return nums[0] + nums[1] + nums[2] 
        
        nums.sort()
        closestSum = nums[0] + nums[1] + nums[2] - target
        for i in range(len(nums)-2):
            if 0 < i and nums[i-1] == nums[i]:
                continue
            
            l, r = i+1, len(nums)-1
            
            while l < r:
                s = nums[i] + nums[l] + nums[r]
                if abs(s - target) < abs(closestSum - target):
                    closestSum = s

                if s <= target:
                    l += 1
                elif s > target:
                    r -= 1
                else:
                    return closestSum

        return closestSum

시간복잡도는 O(nlogn) : for문(n)에 이진탐색트리(logn) 공간복잡도는 O(1) : 상수 l,r,s 선언