当前位置：首页 > article >正文

最接近的三数之和

article 2025/3/31 18:23:33

给你一个长度为 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）。

提示：

3 <= nums.length <= 1000
-1000 <= nums[i] <= 1000
-104 <= target <= 104

解题思路：

初始化最接近值
- 初始设为前三个数的和（nums[0] + nums[1] + nums[2]），作为基准。
三重循环枚举所有组合
- 第一层循环（i）：固定第一个数 nums[i]。
- 第二层循环（j）：在 i 之后固定第二个数 nums[j]。
- 第三层循环（k）：在 j 之后遍历第三个数 nums[k]，计算三数之和 sum。
动态更新最接近值
- 如果 sum == target，直接返回（已找到最优解）。
- 否则，比较 sum 与 target 的绝对差，更新最接近值 closest。
返回结果
- 遍历完成后，closest 即为最接近 target 的三数之和。

代码：

#include <stdlib.h> // 用于 abs()
int threeSumClosest(int* nums, int numsSize, int target) {
    if (numsSize < 3)
    return 0;
    int closest = nums[0] + nums[1] + nums[2]; // 初始值
    for (int i = 0; i < numsSize - 2; i++) {
        for (int j = i + 1; j < numsSize - 1; j++) {
            for (int k = j + 1; k < numsSize; k++) {
                int sum = nums[i] + nums[j] + nums[k];
                // 如果等于 target，直接返回（最优解）
                if (sum == target) {
                    return sum;
                }
                // 更新最接近的值
                if (abs(sum - target) < abs(closest - target)) {
                    closest = sum;
                }
            }
        }
    }
    return closest;
}