【算法day15】最接近的三数之和

16. 最接近的三数之和

给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。

这里是引用
返回这三个数的和。
假定每组输入只存在恰好一个解。

https://leetcode.cn/problems/3sum-closest/submissions/612967700/

class Solution {
public:int threeSumClosest(vector<int>& nums, int target) {// 要使得,a+b+c-target的绝对值最小int min_dist = 100000;int sum = 0;sort(nums.begin(), nums.end());for (int a = 0; a < nums.size(); a++) {for (int b = a + 1; b < nums.size(); b++) {int c = nums.size() - 1;while (b < c) {int cur_dist = abs(nums[a] + nums[b] + nums[c] -target); // 目标尽可能接近0if (cur_dist < min_dist) {min_dist = cur_dist;sum = nums[a] + nums[b] + nums[c];if (cur_dist == 0) {return sum;}}c--;}}}return sum;}
};

官方题解“

class Solution {
public:int threeSumClosest(vector<int>& nums, int target) {int len_nums = nums.size();sort(nums.begin(), nums.end());int min_distance = 100000;int ans = 0;for (int begin = 0; begin < len_nums; begin++) {if (begin > 0 && nums[begin] == nums[begin - 1])continue;int right = len_nums - 1;for (int mid = begin + 1; mid < len_nums; mid++) {while (mid < right) {int sum = nums[begin] + nums[mid] + nums[right];if (abs(sum - target) < min_distance) {min_distance = abs(sum - target);ans = nums[begin] + nums[mid] + nums[right];if (min_distance == 0) {return ans;}}// 右侧往左移动if (sum > target) {int right_tmp = right - 1;while (mid < right_tmp &&nums[right_tmp] == nums[right]) {right_tmp--;}right = right_tmp;} else {//最小值只能出现在左侧int mid_tmp = mid + 1;while (mid_tmp < right && nums[mid_tmp] == nums[mid]) {mid_tmp++;}mid = mid_tmp;}}}}return ans;}
};