16. 最接近的三数之和

野性酷女 2021-11-02 11:58 217阅读 0赞

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

例如，给定数组 nums = [-1，2，1，-4], 和 target = 1.
    
    与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).

1 public class ThreeSumClosest {
     2     //方法：双指针法，需要先对数组进行排序，固定一个值，其余两指从两端逐步向中间查询
     3     public static int threeSumClosest(int[] nums, int target) {
     4         int minDifference = Integer.MAX_VALUE;
     5         int len = nums.length;
     6         int res = 0;
     7         quickSort(nums, 0, len-1);  //先对数组进行排序，练习一下快排
     8         for(int i=0; i<len-2; i++) {  //数组中后两个数无需计算
     9             int value = target - nums[i];  //三数中后两个数的目标和
    10             int left = i+1;
    11             int right = len-1;
    12             while(left < right) {
    13                 int temp = nums[left] + nums[right];
    14                 if(value == temp) {  //如果两数的值等于目标和，则肯定是最接近的，直接返回
    15                     return target;
    16                 }
    17                 int chazhi = value - temp > 0 ? value -temp : temp - value;  //计算得到差值的绝对值。因为是最接近的，可能大于也可能小于
    18                 if(chazhi < minDifference) {  //比较当前差值和记录最小差值的大小，小于则使用当前差值
    19                     minDifference = chazhi;
    20                     res = nums[i] + temp;
    21                 }
    22                 if(value < temp) {
    23                     right--;
    24                 }else {
    25                     left++;
    26                 }
    27             }
    28         }
    29         return res;
    30     }
    31     public static void quickSort(int[] nums, int start, int end) {
    32         if(start >= end) {
    33             return;
    34         }
    35         int left = start;
    36         int right = end;
    37         int temp = nums[left];
    38         while(left < right) {
    39             while(left < right && nums[right] >= temp) {
    40                 right--;
    41             }
    42             nums[left] = nums[right];
    43             while(left < right && nums[left] <= temp) {
    44                 left++;
    45             }
    46             nums[right] = nums[left];
    47         }
    48         nums[left] = temp;
    49         quickSort(nums, start, left-1);
    50         quickSort(nums, left+1, end);
    51     }
    52 }

转载于:https://www.cnblogs.com/xiyangchen/p/10922847.html