【力扣算法01】之最接近的三数之和

简介: 【力扣算法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

解题思路


  1. 首先定义了一个名为Solution的类,该类继承自object
  2. 在类中定义了一个名为threeSumClosest的方法,该方法有两个参数:numstarget,分别表示给定的整数数组和目标值。
  3. nums.sort()将数组nums进行排序,这是为了方便后续的双指针遍历。
  4. closest_sum初始化为正无穷大,用于存储最接近目标值的和。
  5. 使用一个循环遍历数组nums,循环变量i的取值范围为从0到数组长度减2。
  6. 在循环中,使用两个指针leftright分别指向当前元素后面的第一个和最后一个元素。
  7. 进入一个内部的循环,当left小于right时进行迭代:
  • 计算当前三个数的和,即current_sum = nums[i] + nums[left] + nums[right]
  • 如果current_sum等于目标值target,则直接返回current_sum
  • 如果当前和与目标值的差的绝对值小于最接近和与目标值的差的绝对值:
  • 更新最接近的和为当前和:closest_sum = current_sum
  • 如果当前和小于目标值,将左指针右移:left += 1
  • 否则,当前和大于目标值,将右指针左移:right -= 1
  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)

完结


接下来一段时间会主攻算法面试相关问题, 有兴趣的朋友关注专栏哦!!!

相关文章
|
2月前
|
算法
Leetcode 初级算法 --- 数组篇
Leetcode 初级算法 --- 数组篇
43 0
|
1月前
|
存储 算法 Java
leetcode算法题-有效的括号(简单)
【11月更文挑战第5天】本文介绍了 LeetCode 上“有效的括号”这道题的解法。题目要求判断一个只包含括号字符的字符串是否有效。有效字符串需满足左括号必须用相同类型的右括号闭合,并且左括号必须以正确的顺序闭合。解题思路是使用栈数据结构,遍历字符串时将左括号压入栈中,遇到右括号时检查栈顶元素是否匹配。最后根据栈是否为空来判断字符串中的括号是否有效。示例代码包括 Python 和 Java 版本。
|
2月前
|
算法
【链表】算法题(二) ----- 力扣/牛客
【链表】算法题(二) ----- 力扣/牛客
|
2月前
|
算法
【链表】算法题(一) ----- 力扣 / 牛客
【链表】算法题(一) ----- 力扣 / 牛客
|
2月前
|
算法
【顺序表】算法题 --- 力扣
【顺序表】算法题 --- 力扣
|
4月前
|
算法
测试工程师的技能升级:LeetCode算法挑战与职业成长
这篇文章通过作者亲身体验LeetCode算法题的过程,探讨了测试工程师学习算法的重要性,并强调了算法技能对于测试职业成长的必要性。
80 1
测试工程师的技能升级:LeetCode算法挑战与职业成长
|
4月前
|
算法
LeetCode第16题最接近的三数之和
该文章介绍了 LeetCode 第 16 题最接近的三数之和的解法,与第 15 题类似,通过双指针法减少循环次数,根据差值的绝对值来更新最接近的和,并总结了双指针可减少循环次数的要点。
|
4月前
|
算法 Java
LeetCode经典算法题:矩阵中省份数量经典题目+三角形最大周长java多种解法详解
LeetCode经典算法题:矩阵中省份数量经典题目+三角形最大周长java多种解法详解
57 6
|
4月前
|
存储 算法 Java
LeetCode经典算法题:打家劫舍java详解
LeetCode经典算法题:打家劫舍java详解
74 2