16. 3Sum Closest（找出和最接近给定值的三个数）

た入场券 2022-06-08 07:10 248阅读 0赞

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.

For example, given array S = {-1 2 1 -4}, and target = 1.
    
        The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

**题目大意：**给定一个长度为n的整型数组和一个整数target，在数组中找出三个数，它们的和最接近target。可以认为对于每个测试用例，解决方案都是唯一的。

**解题思路：**类似[《15. 3Sum（求数组中和为0的3个数）》][15. 3Sum_0_3]，对于要求三个数的和，可以先对数组从小到大排序，然后锁定一个数nums\[i\]，根据双指针的思路从数组两端到中间遍历，找到两个数nums\[left\]和nums\[right\]，使得nums\[left\]+nums\[right\]+nums\[i\]的和最接近target。遍历过程中使用两个整数diff和res记录当前获得的最优解，其中res表示到目前为止找到的最接近target的三个数的和，diff表示target与res的差的绝对值。当遍历到res==target，已经是最佳方案了，直接返回。

**解题代码：**（22ms，beats 65.39%）

class Solution {
        public int threeSumClosest(int[] nums, int target) {
            int diff = Integer.MAX_VALUE;
    		int res = 0;
    		int len = nums.length;
    		Arrays.sort(nums);
    		for (int i = 0; i < len; i++) {
    			int left = i + 1;
    			int right = len - 1;
    			while (left < right) {
    				int sum = nums[i] + nums[left] + nums[right];
    				if (sum == target) {
    					return sum;
    				}
    				if (Math.abs(sum - target) < diff) {
    					diff = Math.abs(sum - target);
    					res = sum;
    				}
    				if (sum > target) {
    					right--;
    				} else {
    					left++;
    				}
    			}
    		}
    		return res;
        }
    }

[15. 3Sum_0_3]: http://blog.csdn.net/xiangwanpeng/article/details/77970543