题目大意：
最接近的三数之和
给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。
例如，给定数组 nums = [-1，2，1，-4], 和 target = 1. 与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=16
解题思路分析：
本题是Sum系列的又一个经典续集大作。总结下之前的系列文章：
关于本题，因为要计算三个数，如果靠暴力枚举的话时间复杂度会到 O(n^3)，需要降低时间复杂度。我们可以先将数组排序，然后从下标0循环至数组末尾，循环中当前数字nums[i]作为第一个数字。另外在当前循环中，我们定义左右双指针，左指针left指向i+1，右指针right指向数组末尾，这样 nums[i]+nums[left]+nums[right] 可以组成一个三数之和。我们用该和与target进行比较。如果当前和更接近target，则更新返回结果为当前和。如果当前和等于target，直接返回即可。接下来，如果当前和大于target，我们将右指针减一，反之如果当前和小于target，我们将左指针加一。直到左指针等于右指针为止，退出双指针循环。返回上层循环，增加i值，重复此操作。
实现代码：
public int threeSumClosest(int[] nums, int target) {
Arrays.sort(nums); // 排序数组
// 三数之和与target之间的最小差值
int diff=Integer.MAX_VALUE;
// 返回结果。与target最近接的三数之和
int res=0;
// 循环第一个数
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];
// 如果三数之和等于target，直接返回
if(sum==target) return sum;
// 计算三数之和与target之间的差值
int d=Math.abs(sum-target);
// 如果该差值小于全局最小差值
if(d<diff) {
// 更新全局最小差值
diff=d;
// 更新当前三数之和为返回结果
res=sum;
}
// 如果三数之和大于target，右指针减一
if(sum>target) right--;
// 反之左指针加一
else left++;
}
}
return res;
} 本题解法执行时间为3ms。
Runtime: 3 ms, faster than 98.50% of Java online submissions for 3Sum Closest.
Memory Usage: 39.7 MB, less than 6.67% of Java online submissions for 3Sum Closest.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-16-3sum-closest-解题思路分析/