【力扣算法01】之最接近的三数之和
前言
近期已经将python 的大部分内容讲完了, 接下来的一段时间会着重于算法和面试题相关的内容, 确保学有所用, 同时也为准备进入大厂的童靴们做个铺垫, 记得关注哦!!
问题描述
给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们 的和与 target 最接近。 返回这三个数的和。 假定每组输入只存在恰好一个解。
示例 1
输入：nums = [-1,2,1,-4], target = 1
输出：2
解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。 示例 2
输入：nums = [0,0,0], target = 1
输出：0提示
3 <= nums.length <= 1000
-1000 <= nums[i] <= 1000
-104 <= target <= 104解题思路
- 首先定义了一个名为
Solution的类，该类继承自object。 - 在类中定义了一个名为
threeSumClosest的方法，该方法有两个参数：nums和target，分别表示给定的整数数组和目标值。 nums.sort()将数组nums进行排序，这是为了方便后续的双指针遍历。closest_sum初始化为正无穷大，用于存储最接近目标值的和。- 使用一个循环遍历数组
nums，循环变量i的取值范围为从0到数组长度减2。 - 在循环中，使用两个指针
left和right分别指向当前元素后面的第一个和最后一个元素。 - 进入一个内部的循环，当
left小于right时进行迭代：- 计算当前三个数的和，即
current_sum = nums[i] + nums[left] + nums[right]。 - 如果
current_sum等于目标值target，则直接返回current_sum。 - 如果当前和与目标值的差的绝对值小于最接近和与目标值的差的绝对值：
- 更新最接近的和为当前和：
closest_sum = current_sum。
- 更新最接近的和为当前和：
- 如果当前和小于目标值，将左指针右移：
left += 1。 - 否则，当前和大于目标值，将右指针左移：
right -= 1。
- 计算当前三个数的和，即
- 当双指针遍历结束后，返回最接近的和
closest_sum。
通过排序数组和使用双指针的方法，找到一个与目标值最接近的三数之和。通过不断更新最接近的和，并根据当前和与目标值的大小关系移动指针，逐步逼近目标值。经过遍历后得到的最接近的和将作为结果返回。
代码分析
class Solution(object):
def threeSumClosest(self, nums, target):
nums.sort() # 排序数组
closest_sum = float('inf') # 初始化最接近的和为正无穷大- 这段代码定义了一个名为Solution的类，继承自object。
- 类中定义了一个名为threeSumClosest的方法，该方法有两个参数：nums和target，分别表示给定的整数数组和目标值。
- nums.sort()对数组nums进行排序，使得后续的双指针遍历更加方便。
- closest_sum初始化为正无穷大，用于存储最接近目标值的和。
for i in range(len(nums) - 2):
left = i + 1 # 左指针
right = len(nums) - 1 # 右指针- 这段代码使用循环遍历数组nums，循环变量i的取值范围是从0到数组长度减2。
- 在循环中，定义了两个指针left和right，分别指向当前元素后面的第一个和最后一个元素。
while left < right:
current_sum = nums[i] + nums[left] + nums[right] # 当前三个数的和
if current_sum == target: # 如果等于目标值，则直接返回
return current_sum
if abs(current_sum - target) < abs(closest_sum - target): # 更新最接近的和
closest_sum = current_sum
if current_sum < target: # 如果当前和小于目标值，左指针右移
left += 1
else: # 如果当前和大于目标值，右指针左移
right -= 1- 这段代码进入一个内部的循环，当left小于right时进行迭代。
- 在内部循环中，计算当前三个数的和current_sum = nums[i] + nums[left] + nums[right]。
- 如果current_sum等于目标值target，则直接返回current_sum。
- 如果当前和与目标值的差的绝对值小于closest_sum与目标值的差的绝对值，将最接近的和closest_sum更新为current_sum。
- 如果当前和小于目标值，将左指针left右移。
- 如果当前和大于目标值，将右指针right左移。
return closest_sum- 当双指针遍历结束后，返回最接近的和closest_sum。
完整代码
class Solution(object):
def threeSumClosest(self, nums, target):
nums.sort() # 排序数组
closest_sum = float('inf') # 初始化最接近的和为正无穷大
for i in range(len(nums) - 2):
left = i + 1 # 左指针
right = len(nums) - 1 # 右指针
while left < right:
current_sum = nums[i] + nums[left] + nums[right] # 当前三个数的和
if current_sum == target: # 如果等于目标值，则直接返回
return current_sum
if abs(current_sum - target) < abs(closest_sum - target): # 更新最接近的和
closest_sum = current_sum
if current_sum < target: # 如果当前和小于目标值，左指针右移
left += 1
else: # 如果当前和大于目标值，右指针左移
right -= 1
return closest_sum运行效果如图
执行示例代码1
nums = [-1, 2, 1, -4]
target = 1
solution = Solution()
result = solution.threeSumClosest(nums, target)
print(result) 
执行示例代码2
nums = [0, 0, 0]
target = 1
solution = Solution()
result = solution.threeSumClosest(nums, target)
print(result)
完结
接下来一段时间会主攻算法面试相关问题， 有兴趣的朋友关注专栏哦！！！
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2023-07-10，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
腾讯云开发者
