LeetCode 16. 3Sum Closest

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).

解析：
根据输入的一组int类型的数据，从中找出3个数，使3数之和与给定的目标值最接近。每一组输入都会有一个返回结果。
这个题目跟3sum类似，只不过这里要求最接近的数值，方法类似，时间复杂度同样是\(O(n^2)\)。首先对输入数组进行排序，然后记录最小差值，同时记录差值对应的和。
具体具体代码如下：
[cc lang=”C++”]
class Solution {
public:
int threeSumClosest(vector& nums, int target) {
int result = 0;
int min_gap = INT_MAX;
sort(nums.begin(), nums.end());
for(auto it=nums.begin(); it != prev(nums.end(),2); ++it)
{
auto left = next(it);
auto right = prev(nums.end());
while(left < right) { int sum = *it + *left + *right; int gap = abs(sum - target); if(gap < min_gap) { result = sum; min_gap = gap; } if(sum < target) ++ left; else -- right; } } return result; } }; [/cc] 参考： https://siddontang.gitbooks.io/leetcode-solution/content/array/sum.html