Java练习题——(一)最接近的三数之和

发布于 2023-07-10  299 次阅读


题目描述:

给你一个长度为 n 的整数数组 nums和 一个目标值 target。请你从 nums中选出三个整数,使它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在恰好一个解。

示例1:

输入:nums = [-1,2,1,-4],target=1

输出:2

示例2:

输入:nums = [0,0,0],target=1

输出:0

解题思路:

解题1:逐步遍历

最原始的方法也是最开始我的解题思路,就是不惜耗费大量的时间来进行遍历运算。即使用三层遍历,分别将指针右移使得对每个数字组合都进行判断。这样做的好处是简单,代码结构简单。但是坏处就是时间复杂度高,运行速度和效率低下。

源码:

public int threeSumClosest(int[] nums, int target) {
        int i,j,k,sum;
        sum = 0;
        int last = 0;
        int max=0,min=0;
        i = j = k = 0;
        //从左边开始遍历
        for(i = 0;i<nums.length;i++)
        {
            //从第二个位置开始遍历
            for(j = i+1;j<nums.length;j++)
            {
                //从第三个位置开始遍历
                for(k = j+1;k<nums.length;k++)
                {

                    sum = nums[i]+nums[j]+nums[k];
                    if(k == 2)
                    {
                        last = sum;
                        min = java.lang.Math.abs(last-target);
                    }

                    max = java.lang.Math.abs(sum-target);
                    if(max < min) {
                        min = max;
                        last = sum;
                    }
                }
            }
        }
        return last;
}

这种方法在实际中并不能很好的满足性能要求和实际需求,因此我们介绍第二种方法。

解题2:排序+双指针

题目要求找到与目标值 target\textit{target}target 最接近的三元组,这里的「最接近」即为差值的绝对值最小。我们可以考虑直接使用三重循环枚举三元组,找出与目标值最接近的作为答案,时间复杂度为 O(N3)O(N^3)O(N3)。然而本题的 NNN 最大为 100010001000,会超出时间限制。

那么如何进行优化呢?我们首先考虑枚举第一个元素 aaa,对于剩下的两个元素 bbb 和 ccc,我们希望它们的和最接近 target−a\textit{target} - atarget−a。对于 bbb 和 ccc,如果它们在原数组中枚举的范围(既包括下标的范围,也包括元素值的范围)没有任何规律可言,那么我们还是只能使用两重循环来枚举所有的可能情况。因此,我们可以考虑对整个数组进行升序排序,这样一来:

假设数组的长度为 nnn,我们先枚举 aaa,它在数组中的位置为 iii;

为了防止重复枚举,我们在位置 [i+1,n)[i+1, n)[i+1,n) 的范围内枚举 bbb 和 ccc。

当我们知道了 bbb 和 ccc 可以枚举的下标范围,并且知道这一范围对应的数组元素是有序(升序)的,那么我们是否可以对枚举的过程进行优化呢?

答案是可以的。借助双指针,我们就可以对枚举的过程进行优化。我们用 pbp_bpb​ 和 pcp_cpc​ 分别表示指向 bbb 和 ccc 的指针,初始时,pbp_bpb​ 指向位置 i+1i+1i+1,即左边界;pcp_cpc​ 指向位置 n−1n-1n−1,即右边界。在每一步枚举的过程中,我们用 a+b+ca+b+ca+b+c 来更新答案,并且:

如果 a+b+c≥targeta+b+c \geq \textit{target}a+b+c≥target,那么就将 pcp_cpc​ 向左移动一个位置;

如果 a+b+c<targeta+b+c < \textit{target}a+b+c<target,那么就将 pbp_bpb​ 向右移动一个位置。

这是为什么呢?我们对 a+b+c≥targeta+b+c \geq \textit{target}a+b+c≥target 的情况进行一个详细的分析:

如果 a+b+c≥targeta+b+c \geq \textit{target}a+b+c≥target,并且我们知道 pbp_bpb​ 到 pcp_cpc​ 这个范围内的所有数是按照升序排序的,那么如果 pcp_cpc​ 不变而 pbp_bpb​ 向右移动,那么 a+b+ca+b+ca+b+c 的值就会不断地增加,显然就不会成为最接近 target\textit{target}target 的值了。因此,我们可以知道在固定了 pcp_cpc​ 的情况下,此时的 pbp_bpb​ 就可以得到一个最接近 target\textit{target}target 的值,那么我们以后就不用再考虑 pcp_cpc​ 了,就可以将 pcp_cpc​ 向左移动一个位置。

同样,在a+b+c<target时:

如果 a+b+c<targeta+b+c < \textit{target}a+b+c<target,并且我们知道 pbp_bpb​ 到 pcp_cpc​ 这个范围内的所有数是按照升序排序的,那么如果 pbp_bpb​ 不变而 pcp_cpc​ 向左移动,那么 a+b+ca+b+ca+b+c 的值就会不断地减小,显然就不会成为最接近 target\textit{target}target 的值了。因此,我们可以知道在固定了 pbp_bpb​ 的情况下,此时的 pcp_cpc​ 就可以得到一个最接近 target\textit{target}target 的值,那么我们以后就不用再考虑 pbp_bpb​ 了,就可以将 pbp_bpb​ 向右移动一个位置。

实际上,pbp_bpb​ 和 pcp_cpc​ 就表示了我们当前可以选择的数的范围,而每一次枚举的过程中,我们尝试边界上的两个元素,根据它们与 target\textit{target}target 的值的关系,选择「抛弃」左边界的元素还是右边界的元素,从而减少了枚举的范围。这种思路与 11. 盛最多水的容器 中的双指针解法也是类似的。

小优化:

本题也有一些可以减少运行时间(但不会减少时间复杂度)的小优化。当我们枚举到恰好等于 target\textit{target}target 的 a+b+ca+b+ca+b+c 时,可以直接返回 target\textit{target}target 作为答案,因为不会有再比这个更接近的值了。

另一个优化与 15. 三数之和的官方题解 中提到的类似。当我们枚举 a,b,ca, b, ca,b,c 中任意元素并移动指针时,可以直接将其移动到下一个与这次枚举到的不相同的元素,减少枚举的次数。

源码:

public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int n = nums.length;
        int best = 10000000;

        // 枚举 a
        for (int i = 0; i < n; ++i) {
            // 保证和上一次枚举的元素不相等
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            // 使用双指针枚举 b 和 c
            int j = i + 1, k = n - 1;
            while (j < k) {
                int sum = nums[i] + nums[j] + nums[k];
                // 如果和为 target 直接返回答案
                if (sum == target) {
                    return target;
                }
                // 根据差值的绝对值来更新答案
                if (Math.abs(sum - target) < Math.abs(best - target)) {
                    best = sum;
                }
                if (sum > target) {
                    // 如果和大于 target,移动 c 对应的指针
                    int k0 = k - 1;
                    // 移动到下一个不相等的元素
                    while (j < k0 && nums[k0] == nums[k]) {
                        --k0;
                    }
                    k = k0;
                } else {
                    // 如果和小于 target,移动 b 对应的指针
                    int j0 = j + 1;
                    // 移动到下一个不相等的元素
                    while (j0 < k && nums[j0] == nums[j]) {
                        ++j0;
                    }
                    j = j0;
                }
            }
        }
        return best;
}

分析:

时间复杂度为O(N的平方)

空间复杂度是O(logN)


一花一世界,一叶一菩提。