给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。
例如，给定数组 nums = [-1，2，1，-4], 和 target = 1.
与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).
这个题和之前的的三数之和有非常相近之处：
思路：依然是先排序，然后依次遍历。这里加上点约束来优化，首先是我们要知道，在递增的数组中，越往后遍历三数之和越大，如果（三数之和-target）的值大于当前的差值（正数），那么立刻停止循环。如果等于target则直接返回target。
#include <iostream> #include <vector> #include <algorithm> using namespace std; int threesumclosest(vector<int>& nums, int target) { int len = nums.size(); int dif = int_max; int ans = target; sort(nums.begin(), nums.end()); for (int i = 0; i<len - 2; i++) { for (int j = i + 1; j<len - 1; j++) { for (int k = j + 1; k<len; k++) { //cout << nums[i] << " " << nums[j] << " " << nums[k]; int tdif = (nums[i] + nums[j] + nums[k]) - target; if (tdif == 0) return target; if (abs(tdif)<dif) { dif = abs(tdif); ans = nums[i] + nums[j] + nums[k]; } //cout << " " <<ans<<endl; if (tdif> dif) break; } } } return ans; } int main() { vector<int> a = { 1, 2, 4, 8, 16, 32, 64, 128}; int target=82; int ans=threesumclosest(a,target); std::cout << ans << std::endl; return 0; }
本文来自网络收集，不代表计算机技术网立场，如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址：https://www.ctvol.com/c-cdevelopment/608477.html