016 3Sum Closest[M]

02-25

1 題目描述

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.

難度：Medium

2 題目樣例

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

3 題目分析

題設和前一題3Sum比較相似，只有微小的不同：

保證只有一組最符合題意的返回值。
要返回的是其和與目標數字最接近的三個數，也就是說不一定保證存在三個數恰好之和等於目標數字。

4 思路分析

不僅僅是題設，思路上也和之前的3Sum基本一致。只要針對以下的部分，對3Sum的代碼進行修改即可：

在類似於3Sum的遍歷過程中，只要一直維護三數之和與目標數字的差值，並把差值最小的那組數據記錄並返回即可。排序當然是有必要的了。

代碼實現如下：

class Solution { public: int threeSumClosest(vector<int> &num, int target) { int res = num[0] + num[1] + num[2]; std::sort(num.begin(), num.end()); for (int i = 0; i <=num.size(); i++) { int front = i + 1; int back = num.size() - 1; while (front < back) { int sum = num[i] + num[front] + num[back]; if (abs(sum - target) < abs(res - target)) res = sum; if (sum < target) front++; else if (sum > target) back--; else { front++; back--; } } } return res; } };

5 後記

kSum問題是一類問題，也是面試題中比較常見的題目。有興趣的小夥伴，可以在做完3Sum的這兩道題和4Sum之後，寫一個非暴力演算法的KSum問題通解出來。