leetcode16. 最接近的三数之和

给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。

返回这三个数的和。

假定每组输入只存在恰好一个解。

示例 1：

输入：nums = [-1,2,1,-4], target = 1 输出：2 解释：与 target 最接近的和是 2 (-1 + 2 +1 = 2) 。

一开始参考评论写的代码，使用了三个指针$a$,$b$,$c$

• 其中我们需要保证$a>b>c$，防止出现重复的解
• 为了简化求解，我们要先对数组进行排序
• 因此我们得到
  $nums[a]+nums[b]+nums[c]<=nums[a]+nums[b]+nums[c+1]$
  当$nums[a]+nums[b]+nums[c]>target$的时候，$nums[c+1]$及更大的第三个元素就无需再考虑了
• 此外我们也需要综合考虑三数之和比$target$小的情况

初版代码如下：

class Solution(object):def threeSumClosest(self, nums, target):""":type nums: List[int]:type target: int:rtype: int"""nums.sort()ans = nums[0]+nums[1]+nums[2]c = len(nums)-1for a in range(0,len(nums)-2):for b in range(a+1,len(nums)-1):while nums[a]+nums[b]+nums[c] > target and c > b:c -= 1if c<len(nums)-1:val = nums[a]+nums[b]+nums[c+1]ans = val if abs(val-target)<abs(ans-target) else ansif c > b:val = nums[a]+nums[b]+nums[c]ans = val if abs(val-target)<abs(ans-target) else ansreturn ans

以上方法我理解本质为u单指针的方法，现在考虑用双指针的方法进行编程，从两个方向缩小搜索空间

class Solution(object):def threeSumClosest(self, nums, target):""":type nums: List[int]:type target: int:rtype: int"""nums.sort()ans = nums[0]+nums[1]+nums[2] for a in range(0,len(nums)-2):b,c = a+1,len(nums)-1while(b < c):val = nums[a]+nums[b]+nums[c] #if val == target:#    return val#else:ans = val if abs(val-target)<abs(ans-target) else ansif val < target:b += 1else:c -= 1return ans

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/3sum-closest