leetcode 16. 最接近的三数之和

题目描述

给定一个包括n个整数的数组nums和 一个目标值target。找出 nums中的三个整数,使得它们的和与target最接近。返回这三个数的和。假定每组输入只存在唯一答案。
相关话题: 数组、双指针    难度: 中等
例如,给定数组nums = [-1,2,1,-4], 和 target = 1.
target最接近的三个数的和为2. (-1 + 2 + 1 = 2).
思路:
这道题的解法和三数之和的双指针解法一样,相对两数之和,三数是一种降维操作。
与其说双指针,不如说是三指针,该题用到三个指针left、mid、right
首先对数组进行从小到大的排序,


例如上图是排序后的数组,三个指针

  • left指针初始指向0位置,mid = left + 1right指向最后一个位置
  • 大体思路是,固定left指针后,midright指针会向中间靠拢遍历数组,至于midright的更新则是通过当前三数的和与target比较确定更新mid还是right
    直观地,当前和tmp > target时,为了让tmp变小,更新right指针(right--),否则mid++
  • midright相遇,内循环跳出,更新left指针,重新初始化midright,再做第二步地操作。

  • 正确解法
class Solution {
    public int threeSumClosest(int[] nums, int target) {
        if(nums.length < 3) return 0;
        Arrays.sort(nums);
        int left = 0, mid = 0, right = 0;
        int res = nums[0] + nums[1] + nums[2];
        for(left = 0;left < nums.length;left++){
            mid = left + 1;
            right = nums.length - 1;
            while(mid < right){
                int tmp = nums[left] + nums[mid] + nums[right];
                if(Math.abs(tmp - target) < Math.abs(res - target)){
                    res = tmp;
                }
                if(tmp > target){
                    right--;
                }else{
                    mid++;
                }
            }
        }
        return res;
    }
}
  • bug记录
    刚开始居然以if(Math.abs(tmp - target) > Math.abs(res - target))这个条件来更新mid指针right指针,这是不对的,因为tmp有可能比target大,也有可能比target小,所以根据tmptarget的距离来判断更新midright指针是不对的,应该根据tmptarget的大小更新。
class Solution {
    public int threeSumClosest(int[] nums, int target) {
        if(nums.length < 3) return 0;
        Arrays.sort(nums);
        int left = 0, mid = 0, right = 0;
        int res = nums[0] + nums[1] + nums[2];
        for(left = 0;left < nums.length;left++){
            mid = left + 1;
            right = nums.length - 1;
            while(mid < right){
                int tmp = nums[left] + nums[mid] + nums[right];
                if(Math.abs(tmp - target) > Math.abs(res - target)){
                    right--;
                }else{
                    res = tmp;
                    mid++;
                }
            }
        }
        return res;
    }
}
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。