【Leetcode】 16. 最接近的三数之和

发布时间:2023年12月29日

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

AC:

/*
 * @lc app=leetcode.cn id=16 lang=cpp
 *
 * [16] 最接近的三数之和
 */

// @lc code=start
class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        int best = 1e7;
        auto update = [&](int cur) {
            if(abs(cur - target) < abs(best - target)) {
                best = cur;
            }
        };
        // 枚举 a
        for(int i = 0; i < n; i++) {
            if(i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            int j = i + 1, k = n - 1;
            while(j < k) {
                int sum = nums[i] + nums[j] + nums[k];
                if(sum == target) {
                    return target;
                }
                update(sum);
                if(target < sum) {
                    int k0 = k - 1;
                    while(j < k0 && nums[k] == nums[k0]) {
                        k0--;
                    }
                    k = k0;
                } else {
                    int j0 = j + 1;
                    while(j0 < k && nums[j0] == nums[j]) {
                        j0++;
                    }
                    j = j0;
                }
            }
        }
        return best;
    }
};
// @lc code=end

ac

排序 + 双指针

	auto update = [&](int cur) {
        if(abs(cur - target) < abs(best - target)) {
            best = cur;
        }
    };

这段代码使用了C++中的lambda表达式(lambda expression)来定义一个匿名函数,并将其赋值给变量update。lambda表达式是一种方便的方式,可以在代码中定义并使用简短的函数。

在这个例子中,lambda表达式接受一个整数参数cur,并根据与目标值target的差值来更新变量best。如果curtarget的差值比besttarget的差值更小,那么best的值将被更新为cur

这种写法可以用于解决一些问题,例如在一组数字中找到与目标值最接近的数。通过使用lambda表达式,可以将更新最佳值的逻辑封装在一个函数中,并在需要时进行调用。

请注意,lambda表达式使用了捕获列表(capture list&,表示它可以访问外部作用域中的变量。在这个例子中,lambda表达式可以访问targetbest这两个外部变量。


普及下相关的lambda表达式
C++中的lambda表达式是一种匿名函数,可以在需要函数的地方使用它们,而不必为每个函数定义一个命名函数。lambda表达式的语法如下:

[capture list](parameter list) -> return type { body }

其中,capture list是指定在lambda表达式中使用的变量的列表;parameter list是指定lambda函数的参数的列表;return type是指定lambda函数返回值的类型;body是lambda函数的实际代码。

以下是一个简单的示例,演示了如何在C++中使用lambda表达式进行求和运算:

#include <iostream>

int main() {
    int x = 5;
    int y = 10;

    auto sum = [](int a, int b) { return a + b; };

    std::cout << "The sum is: " << sum(x, y) << std::endl;

    return 0;
}

在上述示例中,我们创建了一个lambda函数sum,使用了两个参数ab,并且指定了它的返回类型为intlambda函数的实际代码是{ return a + b; }。然后,我们调用lambda函数,并打印出返回的结果。

需要注意的是,lambda表达式可以捕获外部变量,即在capture list中列出的变量。在上述示例中,我们没有列出任何变量,因此lambda函数没有捕获任何外部变量。如果要捕获外部变量,可以使用如下语法:

[capture list](parameter list) -> return type { body }

其中的capture list是一个用逗号分隔的变量列表,可以按值或按引用捕获变量。例如,如果要按值捕获变量x,可以使用[x];如果要按引用捕获变量x,可以使用[&x]。如果要同时按值和按引用捕获变量,可以使用[=, &x]的形式。

文章来源:https://blog.csdn.net/qq_54053990/article/details/135284166
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。