给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。
返回这三个数的和。
假定每组输入只存在恰好一个解。
示例 1：
输入：nums = [-1,2,1,-4], target = 1 输出：2 解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。
示例 2：
输入：nums = [0,0,0], target = 1 输出：0
提示：
3 <= nums.length <= 1000-1000 <= nums[i] <= 1000-10e4 <= target <= 10e4
思路：sum = nums[i]+nums[j]+nums[k]；先将数组排序，遍历i，后面的j，k两个数利用双指针的思想，同时在基础上做一些剪枝优化操作，可以提高运行效率
class Solution { public int threeSumClosest(int[] nums, int target) { Arrays.sort(nums); int n = nums.length; int min = Integer.MAX_VALUE; int sum = 0; int res = 0; //在遍历前，可以进行两次优化减枝操作 //若最小的三个元素相加 //遍历第一个元素，剩下两个元素通过双指针去遍历，前提排序 for(int i=0;i<n-2;i++) { //若最小的三个元素相加之和都比目标值大，则可以直接返回三数之和 sum = nums[i] + nums[i+1] + nums[i+2]; if(sum > target) { if(sum - target < min) { res = sum; } } //若该元素和最大的两个元素相加之和比目标值小，则直接记录res和min，然后不用再进行遍历判断 sum = nums[i] + nums[n-1] + nums[n-2]; if(sum < target) { if(target - sum < min) { min = target - sum; res = sum; } continue; } int j = i+1; int k = n-1; while(j < k) { sum = nums[i] + nums[j] + nums[k]; if(sum == target) { return sum; } else if(sum > target) //三数之和比目标值大 { if(sum - target < min) //如果更接近，记录，右指针左移 { min = sum - target; res = sum; } k--; } else if(sum < target) //三数之和比目标值小 { if(target - sum < min) //如果更接近，记录，左指针右移 { min = target - sum; res = sum; } j++; } } } return res; } }