算法每日一练 (10)

💢欢迎来到张胤尘的技术站
💥技术如江河，汇聚众志成。代码似星辰，照亮行征程。开源精神长，传承永不忘。携手共前行，未来更辉煌💥

文章目录

算法每日一练 (10)
- 最接近的三数之和
- - 题目描述
  - 解题思路
  - 解题代码
  - - `c/c++`
    - `golang`
    - `lua`

官方站点：力扣 Leetcode

算法每日一练 (10)

最接近的三数之和

题目地址：最接近的三数之和

题目描述

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

解题思路

首先根据题意处理边界条件，当数组长度等于 3 时，不需要任何处理，直接返回和即可。
然后，对目标数组进行排序，根据集合有序的特点再结合双指针 l 和 r，与目标 target 进行比较：
- 当前三元和小于目标值：移动左指针 l 增加。
- 当前三元和大于目标值：移动右指针 r 减少。
- 当前三元和等于目标值：由于题目答案唯一，则直接返回当前三元和即可。
当每次移动指针之后，重新计算当前三元和，然后更新当前已经遍历到元素的三元和 min_sum 和最小三元和与目标 target 的差值 min_sum_df。
更新时，按照规则：当差值 min_sum_df 最小时，一定有 min_sum 与 target 最为接近。
最后返回三元和 min_sum 即可。

解题代码

`c/c++`

#include <vector>
#include <algorithm>class Solution
{
public:int threeSumClosest(std::vector<int> &nums, int target){int sz = nums.size();if (sz == 3)return nums[0] + nums[1] + nums[2];std::sort(nums.begin(), nums.end());int min_sum = nums[0] + nums[1] + nums[2];int min_sum_df = std::abs(target - min_sum);int i = 0;while (i < sz - 2){int l = i + 1, r = sz - 1;while (l < r){int sum = nums[i] + nums[l] + nums[r];int df = std::abs(target - sum);if (df < min_sum_df){min_sum = sum;min_sum_df = df;}if (sum > target)--r;else if (sum < target)++l;elsereturn sum;}++i;}return min_sum;}
};

`golang`

package mainimport ("math""sort"
)func threeSumClosest(nums []int, target int) int {n := len(nums)if len(nums) == 3 {return nums[0] + nums[1] + nums[2]}sort.Ints(nums)min_sum := nums[0] + nums[1] + nums[2]min_sum_df := math.Abs(float64(target) - float64(min_sum))i := 0for i < n-2 {l, r := i+1, n-1for l < r {sum := nums[i] + nums[l] + nums[r]sum_df := math.Abs(float64(target) - float64(sum))if sum_df < min_sum_df {min_sum = summin_sum_df = sum_df}if sum < target {l++} else if sum > target {r--} else {return sum}}i++}return min_sum
}

`lua`

local function threeSumClosest(nums, target)local n = #numsif n == 3 thenreturn nums[1] + nums[2] + nums[3]endtable.sort(nums)local min_sum = nums[1] + nums[2] + nums[3];local min_sum_df = math.abs(target - min_sum)local i = 1while i < n - 1 dolocal l, r = i + 1, nwhile l < r dolocal sum = nums[i] + nums[l] + nums[r]local sum_df = math.abs(target - sum)if sum_df < min_sum_df thenmin_sum = summin_sum_df = sum_dfendif sum < target thenl = l + 1elseif sum > target thenr = r - 1elsereturn sumendendi = i + 1endreturn min_sum
end