參照： LeetCode15題仇参，三數(shù)之和的思路（http://www.reibang.com/p/dc147505569f）
【Description】
Given an array nums of n integers 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.
Example:
Given array nums = [-1, 2, 1, -4], and target = 1.
The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
【Idea】
- 先排序為有序數(shù)組鲸拥；
- 參考3Sum的思想辐宾，最外層由Index=0遍歷至index=len(nums)-3根欧；
- 第二層循環(huán)：從邊緣遞歸至中間每界，跳出條件為left==right逗堵。其中需要設(shè)置個標記為closest_dis慷妙，不斷與三數(shù)之和到target的距離做判斷，然后存儲最近的和值到closest_sum;當三數(shù)之和等于target時芹枷，直接return結(jié)果衅疙；
- 當遍歷過程中沒有三數(shù)之和==target的case，則返回標記的最近和值鸳慈；
（以上復(fù)雜度為n*n）
image.png
空間復(fù)雜度較差饱溢， 待優(yōu)化
class Solution:
def threeSumClosest(self, nums: List[int], target: int) -> int:
nums = sorted(nums)
closest_dis = abs(nums[0] + nums[1] + nums[-1] - target)
closest_sum = nums[0] + nums[1] + nums[-1]
for i in range(len(nums)-2):
if i > 0 and nums[i] == nums[i - 1]:
continue
temp = target-nums[i]
left = i + 1
right = len(nums) - 1
while left < right:
# print(i, left, right)
# print(nums[i], nums[left], nums[right])
if closest_dis > abs(target - nums[left] - nums[right] - nums[i]):
closest_dis = abs(target - nums[left] - nums[right] - nums[i])
closest_sum = nums[left] + nums[right] + nums[i]
# print(closest_dis, closest_sum)
if nums[left] + nums[right] < temp:
left += 1
elif nums[left] + nums[right] > temp:
right -= 1
else:
return nums[left] + nums[right] + nums[i]
return closest_sum
