[리트코드] 16. 3Sum Closest

16. 3Sum Closest

문제

Given an integer array nums of length n and an integer target, find three integers in nums such that the sum is closest to target.

Return the sum of the three integers.

You may assume that each input would have exactly one solution

taget에 가장 가까운 세 수의 합 찾기

제한사항

• 3 <= nums.length <= 1000
• -1000 <= nums[i] <= 1000
• -104 <= target <= 104

풀이

answer 값은 아무 값이나 3개 고른 값의 합으로 초기화해준다.

기준 포인터를 하나 두고 나머지 범위에서 투 포인터를 움직인다.

mid는 세 수 의 합이다.

mid에서 target를 뺀 절댓값이 answer에서 target을 뺀 절댓값보다 작을 경우 answer를 업데이트해준다.

그 후로 mid 값이 target과 같을 때를 목표로 이진 탐색한다.

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

세 수의 합의 최소값을 구하는 문제이기 때문에 중복을 제거해줄 필요가 없다.