问题：
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).
官方难度：
Medium
翻译：
给定一个长度为n的无序数组S，找出其中的3个整数，使这3个整数的和最接近于一个给定的目标值，返回这3个整数的和。
假定整个数组中的解是唯一的。
例子：
数组S:{ -1,2,1,-4}，目标值target=1。
解为2（-1+2+1=2）。
- 这题的解法，与No.015（3Sum）的解法基本相同，先排序，然后通过外循环遍历+内循环夹逼的方法实现。
- 与3Sum问题不同的是，除了维护上一个值是否与当前值相同，其余的优化方法都不能使用。另外，previous的初始值，不能影响第一次计算。
- 维护一个差值closest，这个值要保证是正数。由于解唯一确定，所以在循环过程中，如果出现closest=0的情况，可以直接返回。注意返回值不是差值，而是三个数值的和。
- 注意入参检查。
解题代码：
// 返回值是数组3个元素的和，不是差值
public static int threeSumClosest(int[] nums, int target) {
if (nums == null || nums.length < 3) {
throw new IllegalArgumentException("Input error");
}
Arrays.sort(nums);
// 初始差值和返回值
int returnNo = Integer.MAX_VALUE;
int closest = Integer.MAX_VALUE;
int previous = Integer.MAX_VALUE;
for (int i = 0; i < nums.length - 2; i++) {
if (nums[i] == previous) {
continue;
}else{
previous = nums[i];
}
// 数组剩余部分夹逼
int left = i + 1;
int right = nums.length - 1;
// 转化为2Sum Closest问题
int remainTarget = target - nums[i];
int sum;
int preLeft = Integer.MIN_VALUE, preRight = Integer.MIN_VALUE;
while (left < right) {
if (nums[left] == preLeft) {
left++;
continue;
}
if (nums[right] == preRight) {
right--;
continue;
}
sum = nums[left] + nums[right];
// 解唯一确定，直接返回
if (remainTarget - sum == 0) {
return sum + nums[i];
}
// 最小值替换，返回值赋值
int temp = Math.abs(remainTarget - sum);
if (temp < closest) {
returnNo = nums[i] + nums[left] + nums[right];
closest = temp;
}
if (remainTarget - sum > 0) {
left++;
} else {
right--;
}
}
}
return returnNo;
}
threeSumClosest
相关链接：
https://leetcode.com/problems/3sum-closest/
PS：如有不正确或提高效率的方法，欢迎留言，谢谢！