Given an integer array nums of length n 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.
Solution
先将原数组排序， 然后枚举起始点，对于起始点后面的俩个数再进行双指针扫描（\(left=st, right=end\)）
点击查看代码
class Solution:
def threeSumClosest(self, nums: List[int], target: int) -> int:
if len(nums)<3:
return 0
sorted_nums = sorted(nums)
dif = 99999999999
def TwoSumClosest(nums, st, tgt):
left, right = st, len(nums)-1
delta = 9999999999
while left<right:
s = nums[left]+nums[right]
if abs(delta)>abs(tgt-s):
delta=tgt-s
if s<tgt:
left+=1
elif s>=tgt:
right-=1
return tgt-delta
for i in range(len(nums)-1):
cand = sorted_nums[i] + TwoSumClosest(sorted_nums, i+1, target-sorted_nums[i])
if abs(dif)>abs(target-cand):
dif = target-cand
return target-dif