算法每日一练-10
目录
算法每日一练 (10)
💢欢迎来到张胤尘的技术站
💥技术如江河，汇聚众志成。代码似星辰，照亮行征程。开源精神长，传承永不忘。携手共前行，未来更辉煌💥
官方站点：
算法每日一练 (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;
else
return sum;
}
++i;
}
return min_sum;
}
};golang
package main
import (
"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 := 0
for i < n-2 {
l, r := i+1, n-1
for 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 = sum
min_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 = #nums
if n == 3 then
return nums[1] + nums[2] + nums[3]
end
table.sort(nums)
local min_sum = nums[1] + nums[2] + nums[3];
local min_sum_df = math.abs(target - min_sum)
local i = 1
while i < n - 1 do
local l, r = i + 1, n
while l < r do
local sum = nums[i] + nums[l] + nums[r]
local sum_df = math.abs(target - sum)
if sum_df < min_sum_df then
min_sum = sum
min_sum_df = sum_df
end
if sum < target then
l = l + 1
elseif sum > target then
r = r - 1
else
return sum
end
end
i = i + 1
end
return min_sum
end🌺🌺🌺撒花！
如果本文对你有帮助，就点关注或者留个👍
如果您有任何技术问题或者需要更多其他的内容，请随时向我提问。
