最接近的三数之和

发表于

这是我参与11月更文挑战的第26天，活动详情查看：2021最后一次更文挑战

leetcode 最接近的三数之和

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

返回这三个数的和。

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

示例 1：

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

示例 2：

1
2
ini复制代码输入：nums = [0,0,0], target = 1
输出：0

解题：三数之和要最接近target，就是这个和与target的差值要最小，那就只能算出每个三数之后，然后取最接近target的和，当然如果有等于target的和那就可以直接返回了。首先需要循环数组的每一个数，然后定义两个指针left、right取循环获取其他两个数（从数组两端），然后相加还得总和，有点像暴力循环的感觉，对于无序的数组这样每次都需要循环获取数组每一个数，那如果数组事先有序就好办多了，两个指针就从当前位置index+1至nums.length - 1位置开始相向移动遍历就行，这样慢慢的可以减少遍历元素的次数，算出三个数之和，与之前的和比较，保证获取最小的差值。left、right两个指针只需要移动一个，移动那个需要判断总和的大小，因为数组有序了，如果总和sum比target大，那说明right指针的数需要小一点才行，所以需要移动right指针，可以加一个判断，如果移动后的元素值与移动前的元素值相等，那之后的获取总和判断是没有意义的，所以可以再移动到一个不相等的元素位置就好，反之就移动left指针，最后直到两个指针相撞，就移动index继续循环到数组结尾。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
scss复制代码class Solution {
    public int threeSumClosest(int[] nums, int target) {
        // 先排序
        Arrays.sort(nums);
        // 总和默认先取前三个数
        int total = nums[0] + nums[1] + nums[2];
        // 二指针循环遍历
        int left;
        int right;
        for (int i = 0; i < nums.length - 1; i++) {
            // 左右指针分别指向当前位置之后的两个边界 然后遍历指针相向移动 知道left>=right结束
            left = i + 1;
            right = nums.length - 1;
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                // 如果直接相等 那就是最接近的了
                if (sum == target) {
                    return target;
                }
                // 保证total取最接近 target 的总和
                if (Math.abs(sum - target) < Math.abs(total - target)) {
                    total = sum;
                }
                // 看下移动哪个指针
                if (sum > target) {
                    // 数组有序的情况下 总和太大了移动右边指针
                    right--;
                } else {
                    // 数组有序的情况下 总和太小了移动左边指针
                    left++;
                }
            }
        }
        return total;
    }
}

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%