LeetCode-16.最接近的三数之和 C++实现

一 题目描述

给你一个长度为 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
解释：与 target 最接近的和是 0（0 + 0 + 0 = 0）。

二.问题思路

解决最接近的三数之和问题，核心思路是排序 + 双指针法，具体步骤如下

1.排序数组

• 目的：将数组升序排列，便于后续双指针操作。

• 作用：排序后，可以通过固定一个数，利用双指针在剩余区间内高效寻找另外两个数

2.初始化最近值

• 初始化 closest_sum 为前三个元素的和，min_distance 为当前和与目标值的距离绝对值。

• 意义：为后续比较提供初始基准值。

3.遍历固定第一个数

• 外层循环：遍历数组，固定第一个数 nums[i]。

  • 跳过重复值：若 i > 0 且 nums[i] == nums[i-1]，跳过当前 i，避免重复计算相同三元组（优化点）。

  • 双指针初始化：left = i + 1，right = n - 1，在区间 [i+1, n-1] 内寻找另外两个数。

 4.双指针寻找目标值

• 内层循环：当 left < right 时：

  1. 计算当前三数之和 sum = nums[i] + nums[left] + nums[right]。

  2. 更新最近值：若当前和与目标的距离 distance 小于 min_distance，则更新 closest_sum 和 min_distance。

  3. 调整指针：

     • 若 sum < target：左指针右移（增大和）。

     • 若 sum > target：右指针左移（减小和）。

     • 若 sum == target：直接返回 sum（此时距离为 0，已最优）。

5.终止条件与返回

• 循环结束：遍历所有可能的 i 后，返回 closest_sum。

• 提前终止：若某次 sum == target，直接返回结果，无需继续计算。

 代码实现

class Solution {
public:int threeSumClosest(vector<int>& nums, int target) {sort(nums.begin(), nums.end());int n = nums.size();int closest_sum= nums[0] + nums[1] + nums[2];int min_distance = abs(target - closest_sum);for (int i = 0;i < n - 2;i++){if (i > 0 && nums[i] == nums[i - 1]) continue;int left = i + 1, right = n - 1;while (left < right){int sum= nums[i] + nums[left] + nums[right];int distance = abs(target - sum);if (distance < min_distance){min_distance = distance;closest_sum = sum;}if (sum < target) {left++; // 需要更大的数，左指针右移}else if (sum > target) {right--; // 需要更小的数，右指针左移}else {return sum; // 和等于目标值，直接返回}}}return closest_sum;}
};