LeetCode16-最接近的三数之和

题目描述

给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。
返回这三个数的和。

假定每组输入只存在恰好一个解。

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

示例 2：
输入：nums = [0,0,0], target = 1
输出：0
解释：与 target 最接近的和是 0（0 + 0 + 0 = 0）。

提示：

• 3 <= nums.length <= 1000
• -1000 <= nums[i] <= 1000
• -104 <= target <= 104

思路

沿用上一题 三数之和 的思路，先对给定的数组进行升序排序，再利用双指针将三层循环转化为两层循环。并且只需要求出最接近的值，并不需要列出三元组，所以相对来说更简单了。

排序之后，随着下标往右移动，三数之和必然越来越大。先固定第一个数（即第一层循环），将 left 指向 i + 1，将 right 指向 length - 1，比较三个数的和 tmp 与 target 的关系。如果 tmp > target，说明 right 指针需要往左移动才能得到更接近 target 的值，反之则应将 left 指针向右移动才能得到更接近 target 的值。重复比较 tmp 与 target，直到 left == right 后变更固定的第一个数，再重复这个过程。

优化：如果 nums[left] = nums[left + 1] 或者 nums[right] = nums[right - 1] 可以跳过，提高效率。

代码实现

思路很清晰，也是提交了 4 次才过 -_-||

import java.util.Arrays;  
  
public class Solution16 {  
    public static int threeSumClosest(int[] nums, int target) {  
        int length = nums.length;  
        if (length < 3) {  
            return 0;  
        }  
        Arrays.sort(nums);  
  
        int closest = Integer.MAX_VALUE;  
        int r = Integer.MAX_VALUE;  
  
        for (int i = 0; i < length - 2; i++) {  
            if (i > 0 && nums[i] == nums[i - 1]) {  
                continue;  
            }  
  
            int left = i + 1;  
            int right = length - 1;  
  
            while (left < right) {  
                if (left > i + 1 && nums[left] == nums[left - 1]) {  
                    left++;  
                    continue;  
                }  
                if (right < length - 1 && nums[right] == nums[right + 1]) {  
                    right--;  
                    continue;  
                }  
  
                int tempTarget = nums[i] + nums[left] + nums[right];  
                int diff = tempTarget - target;  
  
                int absDiff = Math.abs(diff);  
                if (absDiff < closest) {  
                    closest = absDiff;  
                    r = tempTarget;  
                }  
  
                if (diff == 0) {  
                    return tempTarget;  
                } else if (diff < 0) {  
                    left++;  
                } else {  
                    right--;  
                }  
            }  
        }  
  
        return r;  
    }  
  
    public static void main(String[] args) {  
//        int[] nums = {-1, 2, 1, -4};  
//        int[] nums = {-1, 2, 1, -4};  
//        int[] nums = {0, 1, 2};  
//        int[] nums = {0, 0, 1};  
//        int[] nums = {1, 1, 1, 1};  
        int[] nums = {-1000, -5, -5, -5, -5, -5, -5, -1, -1, -1};  
        System.out.println(threeSumClosest(nums, -8));  
    }  
}