Given an array nums of n integers and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly one solution. Example:
Given array nums = [-1, 2, 1, -4], and target = 1.
The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
思路和3sum类似：
要求在数组中找出三个数，其和最接近于给定的target。显然就是要求他们之间的绝对值之差最小。我们使用diff来记录差的绝对值。还是首先sort 数组nums,开始遍历sort之后的数组。先fix一个值，然后采用两个头尾指针来滑动寻找另外两个数。每找到两个数，求出三数之和，然后和给定target求绝对值之差，存入newDiff。然后和diff比较，符合则对diff进行更新。
// tc = o(n^2) sc = o(1)
class Solution {
public int threeSumClosest(int[] nums, int target) {
int closet = nums[0] + nums[1] + nums[2];
int diff = Math.abs(closet - target);
Arrays.sort(nums);
for(int i = 0; i < nums.length; ++i){
int left = i + 1, right = nums.length - 1;
while(left < right){
int sum = nums[i] + nums[left] + nums[right];
int newDiff = Math.abs(sum - target);
if(diff > newDiff){
diff = newDiff;
closet = sum;
}
if(sum < target) left++;
else right--;
}
}
return closet;
}
}
