--- title: 16. 最接近的三数之和 description: 在数组中找到三个数，使它们的和最接近目标值。 date: 2024-03-14 tag: [中等, 数组, 双指针] author: Easy Algo premium: false percentage: 30 --- ## 题目 > leetcode 链接：[最接近的三数之和](https://leetcode.cn/problems/3sum-closest/) 给你一个长度为 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 -10^4 <= target <= 10^4 ``` ## 题解 **题意简化：** 想象一下，你有一堆数字，还有一个目标数字。你需要从这堆数字里挑出三个，让它们的加起来的和尽可能地接近目标数字。最后，你需要告诉我是哪个和最接近目标数字。 **边界值与测试用例：** * **边界值：** * 数组长度为 3：`nums = [1, 2, 3], target = 5` * 数组中存在重复数字：`nums = [0, 0, 0], target = 1` * 目标值非常大或非常小：`nums = [-1, 0, 1], target = 10000` 或 `target = -10000` * **测试用例：** * `nums = [-1, 2, 1, -4], target = 1, Output: 2` * `nums = [0, 0, 0], target = 1, Output: 0` * `nums = [-1, 2, 1, -4], target = -1, Output: -1` * `nums = [1, 1, 1, 0], target = -100, Output: 2` * `nums = [1, 1, -1, -1, 3], target = -1, Output: -1` **解法分析：** | 解法 | 优点 | 缺点 | 时间复杂度 | 空间复杂度 | | ---------------- | -------------------------------------------------------------------- | -------------------------------------------------------------------- | -------- | -------- | | 暴力搜索 | 简单直接，容易理解 | 时间复杂度高，当数组长度较大时效率极低 | O(n^3) | O(1) | | 排序 + 双指针 | 在排序后利用双指针，避免了不必要的计算，效率较高 | 需要先排序，改变了原数组的顺序（如果题目不允许修改原数组，则需要复制一份） | O(n log n) | O(1) | * **复杂度评估方法：** * **时间复杂度：** 主要看循环的次数。暴力搜索需要三重循环，所以是 O(n^3)。排序 + 双指针，排序是 O(n log n)，双指针是 O(n)，所以总的是 O(n log n)。 * **空间复杂度：** 主要看有没有用到额外的存储空间。两种方法都只用了几个变量，所以是 O(1)。 **推荐解法：** 排序 + 双指针。它在时间和空间上都比较平衡，而且也比较容易理解和实现。 **Python代码实现：** **版本一：详细注释** ```python class Solution: def threeSumClosest(self, nums: list[int], target: int) -> int: """ 找到数组中三个数，使其和最接近目标值。 Args: nums (List[int]): 整数数组。 target (int): 目标值。 Returns: int: 最接近目标值的三数之和。 """ # 1. 排序数组，为双指针法做准备 nums.sort() n = len(nums) # 2. 初始化最接近的和为一个较大的值 closest_sum = float('inf') # 3. 遍历数组，以每个元素作为第一个数 for i in range(n - 2): # 4. 使用双指针寻找剩余的两个数 left = i + 1 # 左指针，指向第二个数 right = n - 1 # 右指针，指向第三个数 while left < right: current_sum = nums[i] + nums[left] + nums[right] # 计算当前三个数的和 # 5. 如果当前和等于目标值，直接返回 if current_sum == target: return target # 6. 如果当前和更接近目标值，更新最接近的和 if abs(current_sum - target) < abs(closest_sum - target): closest_sum = current_sum # 7. 根据当前和与目标值的关系，移动指针 if current_sum < target: left += 1 # 如果当前和小于目标值，左指针右移，增大和 else: right -= 1 # 如果当前和大于目标值，右指针左移，减小和 # 8. 返回最接近目标值的和 return closest_sum ``` **版本二：去除注释** ```python class Solution: def threeSumClosest(self, nums: list[int], target: int) -> int: nums.sort() n = len(nums) closest_sum = float('inf') for i in range(n - 2): left = i + 1 right = n - 1 while left < right: current_sum = nums[i] + nums[left] + nums[right] if current_sum == target: return target 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` 进行排序。这是使用双指针的前提。 2. **初始化：** `closest_sum` 初始化为一个很大的值，用于记录最接近目标值的和。 3. **外层循环：** 遍历数组 `nums`，将每个元素 `nums[i]` 作为三元组的第一个数。 4. **双指针：** * `left` 指针指向 `i + 1`，`right` 指针指向数组末尾。 * 在 `while left < right` 的循环中，计算当前三数之和 `current_sum`。 * 如果 `current_sum` 等于 `target`，说明找到了精确解，直接返回 `target`。 * 如果 `current_sum` 比 `closest_sum` 更接近 `target`，则更新 `closest_sum`。 * 如果 `current_sum` 小于 `target`，则将 `left` 右移，以增大 `current_sum`。 * 如果 `current_sum` 大于 `target`，则将 `right` 左移，以减小 `current_sum`。 5. **返回结果：** 循环结束后，`closest_sum` 中存储的就是最接近 `target` 的三数之和。希望这个解答对你有帮助！