描述

在一个包含n个整数的数组S中，查找三个整数，使得这三个整数的和最接近给定值target，假设数组里只有一组这样的数字，写一个函数，返回这三个整数的和。

例如：输入数组S={-1， 2， 1， -4}，目标值target = 1，最接近目标值的和是2，(-1 + 2 + 1 = 2)。

分析

最简单粗暴的方式是把数组里所有的数字三个三个的相加，得出所有的数值后和然后和目标值比较，得出结果。伪代码如下：

target = 1;
dis = INT_MAX;
result = INT_MAX;
for i=0 -> n-2:
    for j=i+1 -> n-1:
        for k=j+1 -> k:
            sum = a[i] + a[j] + a[k];
            curDis = abs(sum - target)
            if curDis < dis:
                dis = curDis;
                result = sum;

不难看出，此种方法的时间复杂度为O()，空间复杂度为O(1)；

有没有降低一些时间复杂度的操作呢？如果把数组排序后有没有可能降低时间复杂度？

在有序数组中，设定三个游标a、b和c：

• 初始值a=0，b=a+1，c=n-1
• 计算a、b和c三个位置元素的和，计算和目标值的差值，差值小于当前的差值则进行替换；
• 和值大于目标值，c游标向前移动(--c)，和值小于目标值b游标向后移动(++b)；
• 结束条件：b>=c

依据以上分析，代码如下：

int threeSumColset(vector<int> &num, int target)
{
    int result = INT_MAX;
    int gap = INT_MAX;
    sort(num.begin(), num.end());
    
    for (auto a=num.begin(); a!=prev(num.end(), 2); ++a) {
        auto b = next(a);
        auto c = prev(num.end());
        
        while (b < c) {
            int sum = *a + *b + *c;
            int curGap = abs(sum - target);
            if (curGap < gap) {
                gap = curGap;
                result = sum;
            }
            if (sum < target) {
                ++b;
            } else {
                --c;
            }
        }
    }
    
    return result;
}

可以看出时间复杂度为O()，空间复杂度为O(1)。

代码在这儿