16. 3Sum Closest

3Sum Closest - LeetCode

정수가 담긴 배열 nums, 특정한 정수 target이 주어진다.

nums의 정수 3개를 골라서 더한 합이 target과 가장 가깝게 되는 정수 3개의 합을 반환하는 문제다.

 

예시

Input: nums = [-1,2,1,-4], target = 1
Output: 2
Explanation: The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

Input: nums = [0,0,0], target = 1
Output: 0

1. 3-Pointer

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        nums.sort()
        answer = 0
        answer_gap = float("inf")
        for i in range(0, len(nums) - 2):
            start, end = i + 1, len(nums) - 1

            while start < end:
                cur = nums[i] + nums[start] + nums[end]
                if abs(cur - target) < answer_gap:
                    answer_gap = abs(cur - target)
                    answer = cur

                if cur < target:
                    start += 1
                elif cur > target:
                    end -= 1
                elif cur == target:
                    return cur

        return answer

3-pointer를 이용해 해결하는 문제다.

3 pointer를 이용해 순회하면서 answer_gap을 작게 만드는 answer를 저장하고 반환하는 것으로 해결할 수 있다.

 

3-pointer를 구현하는 문제는 아래 포스팅을 참고.

15. 3Sum