X

LEETCODE 16. 3Sum Closest 解题思路分析

题目大意:

最接近的三数之和

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

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

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=16

解题思路分析:

本题是Sum系列的又一个经典续集大作。总结下之前的系列文章:


关于本题,因为要计算三个数,如果靠暴力枚举的话时间复杂度会到 O(n^3),需要降低时间复杂度。我们可以先将数组排序,然后从下标0循环至数组末尾,循环中当前数字nums[i]作为第一个数字。另外在当前循环中,我们定义左右双指针,左指针left指向i+1,右指针right指向数组末尾,这样 nums[i]+nums[left]+nums[right] 可以组成一个三数之和。我们用该和与target进行比较。如果当前和更接近target,则更新返回结果为当前和。如果当前和等于target,直接返回即可。接下来,如果当前和大于target,我们将右指针减一,反之如果当前和小于target,我们将左指针加一。直到左指针等于右指针为止,退出双指针循环。返回上层循环,增加i值,重复此操作。

实现代码:

public int threeSumClosest(int[] nums, int target) {
    Arrays.sort(nums); // 排序数组
    // 三数之和与target之间的最小差值
    int diff=Integer.MAX_VALUE;
    // 返回结果。与target最近接的三数之和
    int res=0;
    // 循环第一个数
    for(int i=0;i<nums.length;i++){
        // 左指针作为第二个数字指向第一个数右侧相邻数字
        // 右指针作为第三个数字指向数组最后一位
        int left=i+1, right=nums.length-1;
        // 当左指针小于右指针时循环
        while(left<right){
            // 计算三数之和
            int sum=nums[i]+nums[left]+nums[right];
            // 如果三数之和等于target,直接返回
            if(sum==target) return sum;
            // 计算三数之和与target之间的差值
            int d=Math.abs(sum-target);
            // 如果该差值小于全局最小差值
            if(d<diff) {
                // 更新全局最小差值
                diff=d;
                // 更新当前三数之和为返回结果
                res=sum;
            }
            // 如果三数之和大于target,右指针减一
            if(sum>target) right--;
            // 反之左指针加一
            else left++;
        }
    }
    return res;
}

本题解法执行时间为3ms。

Runtime: 3 ms, faster than 98.50% of Java online submissions for 3Sum Closest.

Memory Usage: 39.7 MB, less than 6.67% of Java online submissions for 3Sum Closest.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-16-3sum-closest-解题思路分析/
Categories: leetcode
kwantong: