最接近的三数之和

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/3sum-closest

题目描述:

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

示例：

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

思路一:

暴力遍历:

• 出事化三个指针,将数组nums所有3个数组合的和与target进行比较,的到最接近的值(不可能有比相等更接近的值，因此如果三数和等于target也可以直接返回).

代码实现：

class Solution {
    public int minNum;
    public int result;
    public int threeSumClosest(int[] nums, int target) {
        int len = nums.length;
        int sum = nums[0] + nums[1] + nums[2];
        // 初始化最小值.
        minNum = Math.abs(sum - target);
        result = sum;
        for (int i = 0; i < len; i++) {
            // 重复元素跳过.
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            int left = i + 1;
            int right = len - 1;
            while (left < right) {
                while (left < right) {
                    if (minNum == 0) return sum;
                    sum = nums[i] + nums[left] + nums[right];
                    int abs = Math.abs(sum - target);
                    if (abs <= minNum) {
                        minNum = abs;
                        result = sum;
                    }  
                    right--;
                }
                left++;
                right = len - 1;
            }
        }
        return result;
    }
}

思路二:

• 对数组进行排序，保证数组从左往右单调递增.
• 初始化三个指针，i从0开始遍历,left = i + 1,right = nums.length - 1;
• 计算三数和sum,如果sum == target，直接返回
• sum > target，则right--,因为数组单调递增,左移right指针可以使三数和sum减小
• sum < target, 则left++,因为数组单调递增,右移left指针可以使三数和sum增加

代码实现:

class Solution {
    public int minNum;
    public int result;
    public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int len = nums.length;
        int sum = nums[0] + nums[1] + nums[2];
        // 初始化最小值.
        minNum = Math.abs(sum - target);
        result = sum;
        for (int i = 0; i < len; i++) {
            // 重复元素跳过.
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            int left = i + 1;
            int right = len - 1;
           
            while (left < right) {
                sum = nums[i] + nums[left] + nums[right];
                int abs = Math.abs(sum - target);
                if (abs <= minNum) {
                    minNum = abs;
                    result = sum;
                }
                // 三数和等于target,直接返回
                if (sum == target) return result;
                // 三数和小于tagrget,增加left(因为数组从左到右递增)
                if (sum < target) left++;
                // 三数和大于tagrget,减小right(因为数组从左到右递增)
                else right--;
            }
        }
        return result;
    }
}