正文
Leetcode 16. 3Sum 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).
这一题和3Sum解法差不多，而且还更简单，因为不用考虑去重的问题。首先排序nums。 然后只要for loop 一下k, 并考虑[i, j]。 每次碰到一个更接近的，就更新一下res。需要注意的是如果current sum = target, 跳出即可。如果cur sum > target, j --，反之 i++.
class Solution(object):
def threeSumClosest(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
n = len(nums)
nums.sort()
res = nums[0] + nums[1] + nums[2] for i in range(n):
j = i + 1
k = n - 1
while j < k:
sum = nums[i] + nums[j] + nums[k] if abs(sum - target) < abs(res - target):
res = sum if sum == target:
return sum
elif sum > target:
k -= 1
else:
j += 1 return res
