Problem:

给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。

例如，给定数组 nums = [-1，2，1，-4], 和 target = 1.

与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/3sum-closest

Answer:

1、暴力解法:时间复杂度O(n^3),超出时间限制。

 

2、O(n^2)的解法:

先将数组排序,对于每一个i从0到n - 1，令left = i + 1，right = size - 1，为了寻找更接近target的三数之和，

若三数之和大于target则让right - 1，若三数之和等于target则返回target，若三数之和小于target则让left + 1。

 

设排序后的数组arr为a, b, c, d, e, f。

令arr[i] = a, arr[left] = b, arr[right] = f。

若a + b + f < target，则令left + 1，即arr[left] = c，

b不再有与小于f的数（如e）组合的可能，但由于e < f，a + b + e < a + b + f，离target更远，因而不必考虑。

 

Code:

1 class Solution: 2     def threeSumClosest(self, nums: List[int], target: int) -> int: 3         nums_len = len(nums) 4         nums.sort() 5         min_dist = float('inf') 6         for i in range(nums_len): 7             left = i + 1 8             right = nums_len - 1 9             while left < right:10                 sum_ = nums[i] + nums[left] + nums[right]11                 dist = abs(target - sum_)12                 if dist < min_dist:13                     min_dist = dist14                     ans = sum_15                 if sum_ == target:16                     return target17                 elif sum_ > target:18                     right -= 119                 else:20                     left += 121         return ans