16. 3Sum Closest

Description

Given an integer array nums of length n and an integer target, find three integers at distinct indices 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 <= 500
• -1000 <= nums[i] <= 1000
• -10⁴ <= target <= 10⁴

Submitted Code

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        nums.sort()
        n = len(nums)
        best_sum = nums[0] + nums[1] + nums[2]

        for i in range(n):
            l, r = i+1, n-1
            while l < r:
                curr_sum = nums[i] + nums[l] + nums[r]

                if abs(curr_sum - target) < abs(best_sum - target):
                    best_sum = curr_sum
                    
                if curr_sum < target:
                    l += 1
                elif curr_sum > target:
                    r -= 1
                else:
                    return curr_sum

        return best_sum

Runtime: 378 ms | Beats 66.77%
Memory: 19.38 MB | Beats 77.31%

Other Solutions

1st

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        nums.sort()
        return self.KSumClosest(nums, 3, target)

    def KSumClosest(self, nums: List[int], k: int, target: int) -> int:
        N = len(nums)
        if N == k:
            return sum(nums[:k])

        # target too small
        current = sum(nums[:k])     # 최소합 계산
        if current >= target:
            return current

        # target too big
        current = sum(nums[-k:])    # 최대합 계산
        if current <= target:
            return current
        
        if k == 1:
            return min([(x, abs(target - x)) for x in nums], key = lambda x: x[1])[0]

        closest = sum(nums[:k])
        for i, x in enumerate(nums[:-k+1]):
            if i>0 and x == nums[i-1]:
                continue
            current = self.KSumClosest(nums[i+1:], k-1, target - x) + x
            if abs(target - current) < abs(target - closest):
                if current == target:
                    return target
                else:
                    closest = current

        return closest

time complexity: 𝑂(𝑛^𝑘-1)
space complexity: 𝑂(𝑛𝑘)

숫자 하나를 선택 후 k - 1 개로 다시 재귀 호출하는 방법으로, 숫자 3개 뿐만 아니라 k개를 더하는 경우에도 적용할 수 있다. 재귀 호출 뿐만 아니라 최소합과 최대합으로 범위를 체크해서 불필요한 탐색을 많이 줄이는 방법을 사용했다.