## 一.题目描述  ## 二.解题技巧 该题与3Sum的要求类似，不同的是要求选出的组合的和与目标值target最接近而不一定相等。但实际上，与3Sum的算法流程思路相似，先是进行排序，然后顺序选择数组A中的下标为i的元素值作为组合中三个数的最小值，进而寻找另外两个更大的值，最后求出三个数的和。不过的地方在于这里是寻找最靠近给定值，寻找最靠近的值就无所有重复的事情了，所以可以不考虑夹逼的过程中的越过相同元素的过程，虽然越过相同的元素速度会快一些，但是代码长度也会加长。 这道题难的地方可能在于刚开始这种差的阈值的过程，如果把阈值设置得太小了，会出现错误，因此，应该尽可能地将阈值设置得大一点。由于数组是已经排序的，因此，数组中三个数的和的范围在[3*A[0], 3*A[n-1]]，因此，阈值可以根据下面三种情况进行设置： ~~~ 1.if target >= 3*A[n-1],阈值设置为H = target - 3 * A[0]; 2.if 3*A[0] <= target<3*A[n-1],阈值设置为H = 3 * A[n-1] - 3*A[0]; 3.if target < 3 * A[0],阈值设置为H = 3 * A[n-1] - target。 ~~~ 这样就可以根据阈值与目前得到的三个数的和与target的差来判断是否是最接近target的情况了，根据不同的情况，选择缩放的方向。 ## 三.示例代码 ~~~ class Solution { public: int threeSumClosest(vector<int> &num, int target) { int Size = num.size(); sort(num.begin(), num.end()); int MaxSum = 3 * num[Size - 1]; int MinSum = 3 * num[0]; int ThreadHold = 0; if (target <= MinSum) { ThreadHold = MaxSum - target; } if (MaxSum < target) { ThreadHold = target - MinSum; } if ((MinSum < target) && (target <= MaxSum)) { ThreadHold = MaxSum - MinSum; } int Result = 0; for (int Index_outter = 0; Index_outter < (Size - 2); Index_outter++) { int First = num[Index_outter]; int Second = num[Index_outter + 1]; if ((Index_outter != 0) && (First == num[Index_outter - 1])) { continue; } int Start = Index_outter + 1; int End = Size - 1; while (Start < End) { Second = num[Start]; int Third = num[End]; int Sum = First + Second + Third; if (Sum == target) { return Sum; } if (Sum < target) { Start++; if (ThreadHold >= (target - Sum)) { Result = Sum; ThreadHold = target - Sum; } } if (Sum > target) { End--; if (ThreadHold >= (Sum - target)) { Result = Sum; ThreadHold = Sum - target; } } } } return Result; } }; ~~~ ## 四.总结 这道题最难的地方在于阈值的选择上面，其实可以设置为整数的最大值的，但是，我一开始并不知道如何计算整数的最大值，因此，只能根据排好序的数组的三个数的和的范围与target的关系来设定阈值了，具体的阈值设置情况可以画个数轴出来分析，画出数轴之后，一切就明显了。