LeetCode #16 2018-07-28

16. 3Sum Closest

Given an array nums of n integers 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:
Given array nums = [-1, 2, 1, -4], and target = 1.
The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

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

这道题跟3Sum很类似，区别就是要维护一个最小的closest，求出和目标最近的三个和。brute force时间复杂度为O(n³)，优化的解法是使用排序之后夹逼的方法，总的时间复杂度为O(n²+nlogn)=(n²), 空间复杂度是O(n)。
代码如下：

class Solution(object):
    def threeSumClosest(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        closest = float('inf')
        if not nums or len(nums) < 3:
            return closest
        
        nums.sort()
        for i, num in enumerate(nums[:len(nums) - 2]):
            two_sum_closest = self.twoSumClosest(nums, i + 1, len(nums) - 1, target - nums[i])
            if abs(two_sum_closest) < abs(closest):
                closest = two_sum_closest
            
        return target + closest
     
    def twoSumClosest(self, nums, left, right, target):
        cur_min = float('inf')
        while(left < right):
            closest = nums[left] + nums[right] - target
            if abs(closest) < abs(cur_min):
                cur_min = closest
            if closest == 0:
                return 0
            if closest > 0:
                right -= 1
            else:
                left += 1
                
        return cur_min

感悟:

1. 审题，题目最后求的是最接近target的3个数的和。所以twoSum中根据target - num[i]求的closest就是与target的差值，所以最后return的target + closest即是他们3个数的和。
2. 注意，这里的closest是有正负的，不是绝对值后的结果，这样才能根据target + closest正确求出3个数的和。