题目难度：Medium
题目：
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.
翻译：
给定一个n个整数的数组S，在S中找到三个整数，使三个数的和最接近目标数，返回三个整数的和。
您可以假设每个输入都有一个确定的答案。
思路：利用3sum里面的算法进行适当调整进行定位。
Code：125 / 125 test cases passed.——27ms(beats 20.85%) 时间复杂度：O(N2)
public int threeSumClosest(int[] nums, int target) {
Arrays.sort(nums);
int result = nums[0] + nums[1] + nums[2];
for (int i = 0; i < nums.length - 2; i++) {
if (i > 0 && nums[i] == nums[i-1])
continue; // 相邻起点相同的情况已经在上一个点都判断过了
int left = i + 1;
int right = nums.length - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right]; // 与3sumy一样
if (Math.abs(sum - target) < Math.abs(result - target)) {
result = sum;
}
// 找3sum时，是找确切的相等，所以找到后，三点的值就确定了，不可能有另一个不同的值可以对其中某一个进行替代（只能同时替换两个）；
// 但是本题就算找到了也不能去重，因为三点不是确定的，有可能用一个点将三点中某一点进行替代形成更接近的数，所以不能用while去重【其实要去也行，需要加一个绝对值判断，见下面解释】
if (sum > target) {
right--;
} else {
left++;
}
}
}
return result;
}
不去重解释：
如果去重，假如num[left]与num[left+1]相同，消除了num[i]+num[left]+num[left+1]是‘’最接近的组合‘’可能
其实要去也不是没有办法，那就把这个可能在去重前进行判断记录即可：
if (left < right
&& nums[left] == nums[left + 1]
&& Math.abs(target - sum) < Math
.abs(target - result)) {
result = nums[i] + nums[left] * 2;
}
if (left < right
&& nums[right] == nums[right - 1]
&& Math.abs(target - sum) < Math
.abs(target - result)) {
result = nums[i] + nums[right] * 2;
}
明显，这种方法仅仅为了那一种情况增加算法复杂度是不明智的，在运行其他测试用例的时候都会慢一点，所以不采用。
参考答案：125 / 125 test cases passed.——26ms(beats 20.85%) 时间复杂度O(N2)
public int threeSumClosest(int[] num, int target) {
int result = num[0] + num[1] + num[num.length - 1];
Arrays.sort(num);
for (int i = 0; i < num.length - 2; i++) {
int start = i + 1, end = num.length - 1;
while (start < end) {
int sum = num[i] + num[start] + num[end];
if (sum > target) {
end--;
} else {
start++;
}
if (Math.abs(sum - target) < Math.abs(result - target)) {
result = sum;
}
}
}
return result;
}
和我的简直一毛一样
啊哈哈哈哈哈！
没想到，仅仅刷题几天，我已经如此强大了！简直百年难得的刷题奇才呀！
实验室路人甲：明明答案更快点。
朕：切，1ms能叫快嘛，我重新submit一下说不定还20ms了，略
实验室路人甲：那你看人家把nums[i]包括进sum了是不是比你少算几次？
朕：
好吧，确实应该把nums[i]包括进去。。。sum在此算法里应该灵活使用，即需要整体值时使用。
在讨论区还有大神将此题答案优化了一下（去重），好吧肯定不是我的去重那么复杂。。。。
Code：125 / 125 test cases passed.——22ms(beats 62.99%) 时间复杂度O(N2)
public int threeSumClosest3(int[] nums, int target) {
Arrays.sort(nums);
int sum = nums[0] + nums[1] + nums[nums.length - 1];
int closestSum = sum;
for(int i = 0; i < nums.length - 2; i++){
if(i==0 || nums[i]!=nums[i-1]){
int left = i + 1, right = nums.length - 1;
while(left < right){
sum = nums[left] + nums[right] + nums[i];
if(sum < target){
//move closer to target sum.已经确定sum比target小了，那么相同的left肯定也是小的
while(left<right && nums[left] == nums[left+1]){
left++;
}
left++;
}else if(sum > target){
//move closer to target sum.
while(left<right && nums[right] == nums[right-1]){
right--;
}
right--;
}else{
return sum;
}
//update the closest sum if needed.
if(Math.abs(target - sum) < Math.abs(target - closestSum)){
closestSum = sum;
}
}
}
}
return closestSum;
}
原来发现在【28行】找到更小值时不能进行去重，可以选择在【11-25行】指针调整的判断里面进行，并且增加了直接返回最优解，厉害厉害