最接近的三数之和

1、参考资料

https://leetcode-cn.com/problems/3sum-closest/

2、题目要求

题目描述

给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。

示例：

输入：nums = [-1,2,1,-4], target = 1 输出：2 解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。

3、代码思路

排序 + 双指针

最接近的三数之和与三数之和题目的思路相近，都是使用排序 + 双指针先将数组排序，使用两层循环，可将时间复杂度降为 O(ⁿ²)，外层使用 for 循环遍历排序之后的数组，内层使用 while 循环 + 双指针，搜索最接近目标值的三数之和假设三数之和用 curSum 表示，目标值用 target 表示，如果 curSum == target，则直接返回 curSum；如果 curSum > target，表示三数之和大于目标值，right 指针左移，尝试减小 curSum；如果 curSum < target，表示三数之和小于目标值，left 指针右移，尝试增大 curSum每次使用当前 curSum 和 target 的差值，与上次的差值 lastDiff 比较，如果这次差值更小，说明三数之和更接近目标值，更新 curSum 和 lastDiff

4、代码实现

代码

/** * @ClassName ThreeSumClosestDemo * @Description TODO * @Author Heygo * @Date 2020/9/3 18:49 * @Version 1.0 */ public class ThreeSumClosestDemo { public static void main(String[] args) { Solution solution = new Solution(); int closestSum = solution.threeSumClosest(new int[]{1, 1, 1, 0}, 1); System.out.println(closestSum); } } class Solution { public int threeSumClosest(int[] nums, int target) { // 对数组进行升序排列 Arrays.sort(nums); // 最接近目标值的三数之和 int closestSum = 0; // 上一次与目标值的差值 int lastDiff = Integer.MAX_VALUE; // 遍历数组，当 i = nums.length - 3时，left = nums.length - 2，right = nums.length - 1，为临界条件 for (int i = 0; i < nums.length - 2; i++) { // 上一次的元素和当前相同，跳过此次循环 if (i > 0 && nums[i] == nums[i - 1]) { continue; } int left = i + 1; // 左指针 int right = nums.length - 1; // 右指针 // 当 left < right 时，证明还有元素待验证(枚举) while (left < right) { // 求三数之和 int curSum = nums[i] + nums[left] + nums[right]; if (curSum == target) { // 如果等于目标值则直接返回 return curSum; } else if (curSum > target) { // 如果大于目标值，则说明需要尝试减小 curSum，所以 right 指针左移 right--; } else { // 如果小于目标值，则说明需要尝试增大 curSum，所以 left 指针左移 left++; } // 如果这次的差值比上次的差值小，说明这次更接近目标值 if (Math.abs(curSum - target) < lastDiff) { closestSum = curSum; lastDiff = Math.abs(curSum - target); } } } return closestSum; } }