关于java:LeetCode016最接近的三数之和

56次阅读

共计 1296 个字符，预计需要花费 4 分钟才能阅读完成。

题目形容：给定一个包含 n 个整数的数组 nums 和一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最靠近。返回这三个数的和。假设每组输出只存在惟一答案。

示例阐明请见 LeetCode 官网。

起源：力扣（LeetCode）
链接：https://leetcode-cn.com/probl…
著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。

解法一：双指针法

首先将数组排序，获取一个初始的后果 difference，而后第一个数字first 从第一个数字开始遍历，第二个数字 second 和第三个数字 third 别离从之后的数组中从两边向两头遍历，遍历过程中如果与 target 比difference更靠近，则更新 difference，直到遍历实现，返回difference 对应的result。

阐明：解法和 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));
    }
}