这篇很短的博客包括以下几个部分：

 

题目：

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

分析：

1. 对数组进行排序
2. 因为要使得3个数字的和相加和target最接近，那么使用3个指针来处理
   1. 第一个指针i从头开始遍历整个数组
   2. 第二个指针j从i+1开始
   3. 第三个指针k从n-1开始（n为数组长度）
3. 当i固定时，j和k做以下处理，直到j>=k：
   1. 如果sum (=num[i]+num[j]+num[k])小于target，j++
   2. 如果sum大于target，k—
   3. 如果sum等于target，函数返回0
4. 在这个过程中记录下|target-sum|的最小值

真的不难。一头一尾两个指针，这算是什么思想呢……姑且认为是"排除法"好了╮(╯▽╰)╭。在任何一个时刻，i或j都只有一个可能的移动方向，因为[i+1,j-1]和[k+1,n-1]两段已经被排除了。

代码：

#include <vector>

#include <algorithm>

using namespace std;

 

class Solution

{

public:

    int threeSumClosest(vector<int> &num, int target)

    {

        if(num.size() < 3) return 0;

 

        sort(num.begin(), num.end());

 

        int mindiff = num[0]+num[1]+num[2]-target;

 

        for(int i = 0; i < num.size()-2; i++)

        {

            int j = i+1;

            int k = num.size()-1;

 

            while(j < k)

            {

                int diff = num[i]+num[j]+num[k]-target;

                mindiff = (abs(diff) < abs(mindiff)) ? diff : mindiff;

 

                if(diff < 0)

                    j++;

                else if(diff > 0)

                    k--;

                else

                    break;

            }

 

            if(mindiff == 0) break;

        }

 

        return mindiff+target;

    }

};