题目
问题网址：
https://leetcode.com/problems/3sum-closest/description/
问题描述：
Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.
For example, given array S = {-1 2 1 -4}, and target = 1.The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
解决方法
主要思想：
主要思想来自Leetcode problem16的讨论区(https://leetcode.com/problems/3sum-closest/discuss/7873/A-n2-Solution-Can-we-do-better)，主要思想如下：
Step1： 首先将vector v排序（排序后方便控制大小）。
Step2： 对任意元素v[i]，寻找更匹配的v[j]和v[k]，使得target和（nums[i] + nums[j] + nums[k]）最接近。
注意：
1、如果数据只有3个元素，则这3个元素是唯一的可能值，所以直接返回这3个元素即可。
2、i的取值范围是[0, len(v)-3]，因为k>j>i，所以i的最大取值是len(v)-3。
实现代码：
#include <iostream>
#include <vector>
# include <cmath>
#include<algorithm>
using namespace std;int threeSumClosest(vector<int>& nums, int target) {int len = nums.size();sort(nums.begin(), nums.end()); //排序if(len == 3)return nums[0] + nums[1] + nums[2]; //若只有3个元素，则这3个元素便是最佳元素else{int answer = nums[0] + nums[1] + nums[2]; //赋初值，用于下面的比较int i = 0, j = 0, k = 0, sum = 0;for(int i = 0; i < len - 2; ++i){ //控制第一个元素，查找在第一个元素固定的情况下，第二个和第三个元素的最佳取值j = i + 1;k = len - 1;while(j < k){ //设置终止条件，防止重复循环sum = nums[i] + nums[j] + nums[k];if(abs(target - answer) > abs(target - sum)){ //比较answer值和当前sum哪个更合题意answer = sum;}sum < target ? j++ : k--; //若sum比target小，所以我们需要扩大target的值，因此将j++，使得nums[j]变大，从而sum变大，sum更接近target；若sum比target大，我们需要缩小sum的值，因此k--（为什么使nums[k]的值减小，而不增大nums[j]的值呢？因为nums[j]小的那部分的值已经循环过，不需要重复考虑，所以考虑没有循环过的值）。}}return answer;}
}int main()
{int S[] = {
0, 2, 1, -3}, target = 1;vector<int> nums(S, S+sizeof(S)/sizeof(int)); //vector初始化cout << threeSumClosest(nums, target) << endl;return 0;
}
Submission Detail:
125/125 test cases passed.
Status: Accepted
Runtime: 13 ms