[LeetCode] 16. 3Sum Closest

16. 3Sum Closest

Medium

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.

 

Example 1:

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).

Example 2:

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

 

Constraints:

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

---

문제 풀이

• 주어진 양,음수의 숫자 배열에서 숫자 세개를 뽑는다.
• 숫제 세개의 값을 더하고 target 과 가장 가까운 숫자를 찾는다.
• 제한 사항을 보면 숫자들의 최대 갯수는 1000개이다. 
• dfs 로 풀게되면 O(n!) 시간복잡도이기 때문에 시간초과 에러가 발생한다.
• 숫자 갯수가 최대 1000개라서, O(N^2) 시간복잡도의 알고리즘도 사용가능한데
• Two Pointer + sort 를 사용해서 풀자.
• 우선 숫자들을 정렬하고, 배열의 처음 자리부터 순서대로 Two Pointer 를 적용한다. 
• 현재 i 위치의 숫자와, 그 위치보다 1칸 앞의 숫자와, 맨 마지막의 숫자 이렇게 세개의 숫자를 더하면서 값을 구한다. 
• 만약 더한 세개의 값이 target 보다 작으면 왼쪽 포인터를 한칸 땡기고, 반대의 경우 오른쪽 포인터를 땡긴다.

소스 코드

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        d = float('inf')
        nums.sort()
        for i in range(len(nums)):
            l, r = i + 1, len(nums) - 1
            while l < r:
                total = nums[i] + nums[l] + nums[r]
                if abs(target - total) < abs(d):
                    d = target - total
                if total < target:
                    l += 1
                else:
                    r -= 1
            if d == 0:
                break
        return target - d