【力扣算法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)

在这里插入图片描述

完结

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