[알고리즘] 3Sum Closest

포인트

• 이번 알고리즘은 저번에 풀이한 4Sum 문제와 상당히 유사한 문제 입니다. 문제에서 제한된 값의 크기와 입력범위가 크기 때문에. 시간 초과를 예상할 수 있었습니다. 이에 for loop로 한 번, 이분 탐색으로 한 번의 걸쳐 시간 복잡도를 낮춰 해결할 수 있었습니다.

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

3Sum Closest - LeetCode

아래 문제를 같이 보시면 상당히 많은 도움이 될 것 같습니다.

2021.07.16 - [알고리즘] - [알고리즘] 4Sum

[알고리즘] 4Sum

 

🧶문서는 항상 수정될 수 있습니다. 비판은 환영합니다. 

python

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        nums.sort()
        result = nums[0]+nums[1]+nums[2]
        # 일단 정답을 먼저 구한다.
        for i in range(len(nums)-2):
            left = i+1
            right = len(nums)-1

            while left < right:
                # 이러한 부분이 이분 탐색과 비슷하다.
                summation = nums[i] + nums[left] + nums[right]
                if abs(summation-target) < abs(result-target):
                    result = summation
                if summation == target:
                    return target
                elif summation > target:
                    right -= 1
                else:
                    left += 1
        else:
            return result