16. 3Sum Closest

leetcode.com/problems/3sum-closest/

3Sum Closest - LeetCode

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        
        diff = float('inf')
        n = len(nums)
        
        nums.sort()
        
        for i in range(n-2) :
            
            l, r = i+1, n-1

            while l < r :
                
                curr = nums[i] + nums[l] + nums[r]
                
                if curr < target :
                    l += 1
                else :
                    r -= 1
                
                if abs(target-curr) < abs(diff) :
                    diff = target-curr
                    
            if diff == 0 :
                break
                    
        return target-diff
    

정리 :

처음 문제를 접했을때 브루트 포스로 푸는 방법 밖에 생각이 나지 않았음.

브루트 포스로 풀면 시간복잡도가 n의 세제곱이 되는데 정렬을 함으로써 시간복잡도를 쉽게 줄일수 있었음.

Array 관련 문제를 풀경우는 sort를 항상 염두해둘 것.