当前位置 博文首页 > 向日葵的专属太阳：LeetCode16. 最接近的三数之和
题目来源：力扣（LeetCode）
题目描述：
给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。
示例1：
输入：nums = [-1,2,1,-4], target = 1
输出：2
解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。
提示：
3 <= nums.length <= 10^3-10^3 <= nums[i] <= 10^3-10^4 <= target <= 10^4解题思路：
这题与上题类似，如果上题搞懂了，这题应该也不难，只是改变一下判断条件。
LeetCode15. 三数之和
简单说一下思路，首先对 nums 数组进行排序，然后遍历排序后的 nums，要注意跳过重复的组合，然后定义两个指针 left 、right ，当 left < right 时，执行循环，计算 nums[i] + nums[left] + nums[right] 的值，判断该值是否更接近 target ，如果是则替换 similar_num ，然后根据 add 与 target 的大小移动指定指针。
class Solution(object):
def threeSumClosest(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
length = len(nums)
# 赋初值
similar_num = sum(nums[:3])
# 对nums进行排序
nums.sort()
# 遍历排序后的nums
for i in range(length - 2):
# 跳过重复的组合
if i > 0 and nums[i] == nums[i - 1]:
continue
left = i + 1
right = length - 1
while left < right:
add = nums[i] + nums[left] + nums[right]
# 当前的值更接近target，需要替换
if abs(add - target) < abs(similar_num - target):
similar_num = add
# 如果三数之和add小于目标值target，则left右移（值增大）
if add < target:
left += 1
# 如果三数之和add大于目标值target，则right右移（值减小）
elif add > target:
right -= 1
# add等于target，即已找到最相近的三个数，直接返回
else:
return similar_num
return similar_num
