[LeetCode] 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).

[中文翻译] 给定n个整数的数组S，在S中找到三个整数，使得和最接近给定的数字target。 返回三个整数的和。 可以假设每个输入都有且只有一个解。

例如，给定数组S = {-1 2 1 -4}，和target = 1。 最接近target的和为2。（-1 + 2 + 1 = 2）。

[解题思路] 与[LeetCode] 3Sum 解题报告 的思路完全相同，不同的是，现在比较的是与target的距离。

同样来看2Sum Closest问题。 给定数组A, B, C, D, E, F, G, H，已从小到大排序。如果A+H>target，那么B~G+H一定会离target更远（因为数组是有序的）。如果A+H<target，那么A+B~G也一定会里target更远。如果A+H=target，那么已经找到了解。

对于3Sum Closest问题，不过是先确定一个点c，然后目标数值变为target-c，问题就转换为了2Sum Closest问题。效率为O(n²)。

[C++代码]