LeetCode-016-最接近的三数之和 java算法leetcode

最接近的三数之和

题目描述：给定一个包括 n 个整数的数组 nums 和一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。
示例说明请见LeetCode官网。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/probl...
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法一：双指针法

首先将数组排序，获取一个初始的结果difference，然后第一个数字first从第一个数字开始遍历，第二个数字second和第三个数字third分别从之后的数组中从两边向中间遍历，遍历过程中如果与target比difference更接近，则更新difference，直到遍历完成，返回difference对应的result。
【LeetCode-016-最接近的三数之和】说明：解法和 LeetCode-015-三数之和这个题目的解法类似，可对比参考。

import java.util.Arrays; public class Solution { /** * 双指针法 * @param nums * @param target * @return */ public static int threeSumClosest(int[] nums, int target) { if (nums.length == 3) { return nums[0] + nums[1] + nums[2]; } Arrays.sort(nums); int result = nums[0] + nums[1] + nums[2]; int difference = Math.abs(result - target); // 第一个数字 for (int first = 0; first < nums.length - 2; first++) { //过滤掉重复的 if (first > 0 && nums[first] == nums[first - 1]) { continue; } for (int second = first + 1; second < nums.length - 1; second++) { if (second > first + 1 && nums[second] == nums[second - 1]) { // 过滤掉重复的 continue; }int third = nums.length - 1; while (second < third) { // 当3个数之和比当前的result更接近时，更新result if (Math.abs(nums[first] + nums[second] + nums[third] - target) < difference) { result = nums[first] + nums[second] + nums[third]; difference = Math.abs(result - target); } third--; } } } return result; }public static void main(String[] args) { int[] nums = new int[]{0, 1, 2, 3, 4, 5, 6}; System.out.println(threeSumClosest(nums, 2)); } }