栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

LeetCode腾讯精选练习50题-016.最接近的三数之和

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

LeetCode腾讯精选练习50题-016.最接近的三数之和

目录
      • 题目描述
      • 解题思路 排序+双指针
      • 代码(Java)

题目描述
  • 给定一个长度为 n 的整数数组 nums 和 一个目标值 target。
  • 请从 nums 中选出三个整数,使它们的和与 target 最接近。
  • 返回这三个数的和。
  • 假定每组输入只存在恰好一个解。
example
input  : nums = [-1,2,1,-4], target = 1
output : 2
note   : 与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。

input  : nums = [0,0,0], target = 1
output : 0
解题思路 排序+双指针
  • 先把数组排序

  • 外层循环从头开始遍历,逐个固定遍历到的元素作为三数的第1个数,然后内层循环是在其后方区间使用首尾双指针

  • 根据三数之和确定移动首部指针还是尾部指针

  • 对比每组三数之和tmpSum与target的差值绝对值,不断保留差值绝对值最小的三数之和

  • 最终保留下来的结果就是与target差值绝对值最小的三数之和,即最接近target的三数之和

  • 时间复杂度:O(n^2)

  • 空间复杂度:O(1)

代码(Java)
public class Solution {
    // 推荐参考下方的写法2
    public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        if (nums.length == 3) {
            return nums[0] + nums[1] + nums[2];
        }
        int n = nums.length;
        int bigger = Integer.MAX_VALUE;
        int smaller = Integer.MIN_VALUE;
        for (int i = 0; i < n - 2; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            int j = i + 1;
            int k = n - 1;
            while (j < k) {
                int tmpSum = nums[i] + nums[j] + nums[k];
                if (tmpSum > target) {
                    if (tmpSum <= bigger) {
                        bigger = tmpSum;
                    }
                    k--;
                } else if (tmpSum < target) {
                    if (tmpSum >= smaller) {
                        smaller = tmpSum;
                    }
                    j++;
                } else {
                    return target;
                }
            }
        }
        if (bigger == Integer.MAX_VALUE) {
            return smaller;
        }
        if (smaller == Integer.MIN_VALUE) {
            return bigger;
        }
        int left = target - smaller;
        int right = bigger - target;
        if (left > right) {
            return bigger;
        } else {
            return smaller;
        }
    }

    // 以下为与思路描述更加一一对应的写法
    // 相较于写法1更易读
    public int threeSumClosest2(int[] nums, int target) {
        Arrays.sort(nums);
        int n = nums.length;
        int best = 10001;
        for (int i = 0; i < n; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            int j = i + 1;
            int k = n - 1;
            while (j < k) {
                int tmpSum = nums[i] + nums[j] + nums[k];
                int cur = Math.abs(tmpSum - target);
                int old = Math.abs(best - target);
                if (cur < old) {
                    best = tmpSum;
                }
                if (tmpSum > target) {
                    k--;
                } else if (tmpSum < target) {
                    j++;
                } else {
                    return target;
                }
            }
        }
        return best;
    }
}
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/950554.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号