描述
力扣16 最接近三数之和
给你一个长度为 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
解释：与 target 最接近的和是 0（0 + 0 + 0 = 0）。
3 <= nums.length <= 1000
-1000 <= nums[i] <= 1000
-104 <= target <= 104
方法：遍历＋双指针
思路：
我们先将数组进行排序，然后遍历，每次遍历先确定一个数字，再通过左右指针确定第二位和第三位。详细解释请看下文代码和注释
具体实现及注释：
class Solution {public int threeSumClosest(int[] nums, int target) {Arrays.sort(nums);int length = nums.length;//这个值为最接近target的三数和，初始化为100000；int close = 100000;//遍历，因为后面至少要留两个数字，所以到length-2即可。for (int i = 0; i < length-2; i++) {int head = nums[i];if (i != 0 && nums[i] == nums[i-1]) continue;//这块代码是速度优化，可以先忽略此部分，先把代码整体逻辑实现理清楚，再来看如何进行优化让代码更快//因为数组是从小到大排序，如果nums[i] + nums[i+1] + nums[i+2]都比target大了，那么后面的元素只会更大，不符合题意，直接和close比较后break打断循环//nums[i] + nums[length-1] + nums[length-2]是选定i的情况下最大和，如果这都比target要小，其余的更小，不符合题意，所以直接continue进入下一次循环/*int sum0 = nums[i] + nums[i+1] + nums[i+2];if (sum0 > target) {if (Math.abs(close - target) > Math.abs(sum0 - target)) close = sum0;break;}int sum1 = nums[i] + nums[length-1] + nums[length-2];if (sum1 < target) {if (Math.abs(close - target) > Math.abs(sum1 - target)) close = sum1;continue;}*///左指针指向第一个数字的后一位，右指针指向最后一个数字int left = i + 1;int right = length - 1;//当三数和sum大于target，说明sum需要减小，所以将右指针左移一位，反之则左指针右移一位while (left < right) {int sum = head + nums[left] + nums[right];if (sum == target) return sum;else if (sum > target) right = nextRight(left, right, nums);else left = nextLeft(left, right, nums);if (Math.abs(close - target) > Math.abs(sum - target)) close = sum;}}return close;}//这个函数是在right左移时过滤掉与当前数值相等的情况，如数组[2, 3, 3, 3, 3],若right=4指向最后一个3,则将前面的3过滤掉，使其等于0指向2.int nextRight(int left, int right, int[]nums) {while (right > left && nums[right] == nums[right-1]) right--;return right - 1;}//与上文同理int nextLeft(int left, int right, int[]nums) {while (right > left && nums[left] == nums[left+1]) left++;return left + 1;}
}
