016 3 sum closest

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

For example, given array S = {-1 2 1 -4}, and target = 1.

The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

Subscribe to see which companies asked this question

思路与3Sum基本相同，现在要额外维护一个表示之前三元组中与目标值的差最小值的变量，这个变量的初始化值应该很大，防止把有意义的三元组直接排除了。此外，由于题目中明确说只有唯一的一组最优解，所有不用考虑重复数字了。

class Solution:
    def threeSumClosest(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        nums.sort()
        i = 0
        result = 0
        distance = pow(2, 32) - 1
        for i in range(len(nums)):
            j = i+1
            k = len(nums) - 1

            while j < k:
                l = [nums[i], nums[j], nums[k]]
                s = sum(l)
                if s == target:
                    return target
                if abs(s - target) < distance:
                    result = s
                    distance = abs(s - target)
                elif s > target:
                    k-= 1
                else:
                    j += 1
        return result

上面的解法已经速度蛮快的了，但是还是很有更快的方法，类似这样，对于已有的一些判断进行判断，速度最终会快很多。

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        if len(nums) < 3:
            return None
        nums.sort()
        result = sum(nums[0:3])

        for i in range(len(nums) - 2):
            if i != 0 and nums[i] == nums[i - 1]:
                continue
            lo, hi = i + 1, len(nums) - 1

            # 分三种情况处理
            # 对于下面的前两种情况就不需要再考虑其他的 lo, hi 组合了
            t1 = nums[i] + nums[lo] + nums[lo + 1]
            t2 = nums[i] + nums[hi - 1] + nums[hi]
            if t1 >= target:
                if abs(t1 - target) < abs(result - target):
                    result = t1
            elif t2 <= target:
                if abs(t2 - target) < abs(result - target):
                    result = t2
            else:
                while lo < hi:
                    s = nums[lo] + nums[i] + nums[hi]
                    if abs(s - target) < abs(result - target):
                        result = s
                    if s == target:
                        return s
                    elif s > target:
                        hi -= 1
                    else:
                        lo += 1
        return result