leetcode 16.最接近的三数之和

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

/*给一个长度为 n 的整数数组 nums 和 一个目标值 target输入: nums = [-1,2,1,-4] target = -1输出: 2 解析: 与 target 最接近的和是 2（-1 + 2 + 1 = 2）
*/
class Solution {
public:int threeSumClosest(vector<int>& nums, int target) {sort(nums.begin(),nums.end()); // O(nlogn)int ans = nums[0] + nums[1] + nums[2];for(int i=0;i<nums.size();++i) {int start = i + 1,end = nums.size() - 1;while(start < end) {int sum = nums[i] + nums[start] + nums[end];if(abs(target - sum) < abs(target - ans)) ans = sum;if(sum > target) end--;else if(sum < target) start++;else return ans;}}return ans;}
};

// -1 2 1 -4  target = 1
/*-4 -1  1  2  |  |  |i  s  e 
*/
// 初始化
// ans : -4 + (-1) + 1 = -4/*-4 -1  1  2  |  |     |i  s     e 
*/
// sum = nums[i] + nums[s] + nums[e] = -3
// abs(target-sum) 和 abs(target-ans)
/*abs(target-sum) = abs(1-(-4)) = 5abs(target-ans) = abs(1-(-3)) = 4 abs(target-sum) < abs(target-ans) 
*/
// ans = sum = -3// 因为 sum(-3) < target(1),所以s右移，有可能效果更好/*-4 -1  1  2  |     |  |i     s  e 
*/
// sum = -4 + 1 + 2 = -1
// abs(target-sum) 和 abs(target-ans)
/*abs(target-sum) = abs(1-(-1)) = 2abs(target-ans) = abs(1-(-3)) = 4 abs(target-sum) < abs(target-ans) 
*/
// ans = sum = -1// 因为 sum(-1) < target(1)，所以s右移，有可能效果更好
/*-4 -1  1  2  |        ||i        es 
*/
// 此时e和s重合,i右移
/*-4 -1  1  2  |  |  |i  s  e 
*/
// sum = -1 + 1 + 2 = 2
// abs(target-sum) 和 abs(target-ans)
/*abs(target-sum) = abs(1-(2)) = 1abs(target-ans) = abs(1-(-1)) = 2 abs(target-sum) < abs(target-ans) 
*/
// ans = sum = 2
// 因为 sum(2) < target(1)，所以e左移，有可能效果更好// 此时e和s重合,i右移
/*-4 -1  1  2  |  ||  i  se
*/
// e和s重合，不足3个数，结束