题目来源：
https://leetcode.com/problems/3sum-closest/
题意分析：
这道题目输入一个数组nums和一个数target，找出数组中三个数，使得他们的和最接近target，返回这三个数的和。
题目思路：
这道题目和上一题3Sum很像，所以也可以用类似的方法去解决这个问题。整个过程分成两步：
①数组排序；这步时间复杂度是（O（nlogn））。
②固定一个数，这步的时间复杂度是（O（n））。
③在剩下的数里面通过“夹逼定理”，找出两个数，使得三个数的和最接近target。这步时间复杂度是（O（n））
总的时间复杂度为（O（nlogn） + O（n）*O(n)） = （O（n^2））。
优化：在第三步的时候通过判断剩下的数中是否最小的两个数相加就大于或者最大两个数就小于target - 第一个数，如果是，则直接判断最小（大）两个数和②中的那个数的和是不是最接近的值。
代码（python）：
1
class
Solution(object):
2
def
threeSumClosest(self, nums, target):
3
"""
4
:type nums: List[int]
5
:type target: int
6
:rtype: int
7
"""
8 size = len(nums)
9if size < 3:
10return 0
11 nums.sort()
12 i = 0 # fix the first index13 ans = nums[0] + nums[1] + nums[size - 1] # ans is used to record the solution14while i < size - 2:
15 tmp = target - nums[i]
16 j = i + 1
17 k = size - 1
18while j < k:
19if nums[j] + nums[k] == tmp:
20return target
21if nums[j] + nums[k] > tmp:
22if nums[j] + nums[j + 1] >= tmp:
23if nums[j] + nums[j + 1] - tmp < abs(ans - target):
24 ans = nums[i] + nums[j] + nums[j + 1]
25break26 tmpans = nums[i] + nums[j] + nums[k]
27if tmpans - target < abs(ans - target):
28 ans = tmpans
29 k -= 1
30else:
31if nums[k] + nums[k - 1] <= tmp:
32if tmp - nums[k] -nums[k - 1] < abs(ans - target):
33 ans = nums[i] + nums[k - 1] + nums[k]
34break35 tmpans = nums[i] + nums[j] + nums[k]
36if target - tmpans < abs(ans - target):
37 ans = tmpans
38 j += 1
39 i += 1
40if ans == target:
41return target
42return ans
转载请注明出处：http://www.cnblogs.com/chruny/p/4830175.html
原文：http://www.cnblogs.com/chruny/p/4830175.html
【说明】：本文章由站长整理发布，文章内容不代表本站观点，如文中有侵权行为，请与本站客服联系(QQ:254677821)！