专栏首页互联网西门二少三数之和姊妹题——LeetCode题目16:最接近的三数之和

三数之和姊妹题——LeetCode题目16:最接近的三数之和

原题描述

+

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

示例

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

输出:2

解释:与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).

原题链接:https://leetcode-cn.com/problems/3sum-closest

思路解析

+

这道题我建议你和下面这道题一起看,因为它们的思路几乎一模一样。下面这道题如果会做,那么本题对你来说会变得相当容易。 LeetCode题目15:三数之和

相对于上面这道题来说,本题容易的地方在于不需要考虑去重,这会让双指针的移动更简单,我再讲一下这里面涉及到的两种情况。

假设我们对数组按升序排序,并以第 处的数字为基础,来寻找它的另外两个同伴,那么在这个有序数组上,我们一定可以通过移动处于 右侧的两个边界指针 和 来实现不断逼近target的目的。

情况1——当nums[i]+nums[L]+nums[R] > target时,我们需要左移 来缩小三数之和,这样才有可能找到与target更接近的值。

情况2——当nums[i]+nums[L]+nums[R] <= target时,我们需要右移 来增加三数之和。

好了,现在可以写代码了。

在LeetCode中不会有重复的题目,但是思路接近可以类比的题目确很多。编程和做数学题一样,需要大量的练习才能强化自己的sense和逻辑性。

复杂度分析

+

  • 时间复杂度:
  • 空间复杂度:

C++参考代码

+

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        int sum = 0;
        if (nums.size() < 2) {
            for (int i = 0; i < nums.size(); ++i) sum += nums[i];
            return sum;
        }

        sort(nums.begin(), nums.end());
        int min_dist = INT_MAX;
        for (int i = 0; i < nums.size() - 2; ++i) {
            int l = i + 1;
            int r = nums.size() - 1;
            while (l < r) {
                int curr_sum = nums[i] + nums[l] + nums[r];
                if (curr_sum < target) {
                    if (target - curr_sum < min_dist) {
                        min_dist = target - curr_sum;
                        sum = curr_sum;
                    }
                    ++l;
                } else {
                    if (curr_sum - target < min_dist) {
                        min_dist = curr_sum - target;
                        sum = curr_sum;
                    }
                    --r;
                }
            }
        }

        return sum;

    }
};

本文分享自微信公众号 - 互联网西门二少(gh_172e639cc498),作者:二环宇少

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-05-31

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • n数之和题目要类比——LeetCode题目18:四数之和

    给定一个包含 n 个整数的数组 nums 和一个目标值 target,判断 nums 中是否存在四个元素 a,b,c 和 d ,使得 a + b + c + d...

    二环宇少
  • LeetCode题目15:三数之和

    给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有满足条件且不重复的三...

    二环宇少
  • LeetCode题目27:移出元素

    给你一个数组 nums 和一个值 val,你需要 原地 移除所有数值等于 val 的元素,并返回移除后数组的新长度。

    二环宇少
  • 画解算法 16-最接近的三数之和

    https://leetcode-cn.com/problems/3sum-closest/

    灵魂画师牧码
  • Q27 Remove Element

    Given an array and a value, remove all instances of that value in-place and retu...

    echobingo
  • 一起刷Leetcode第一篇,数组和字典的妙用

    LeetCode作为一种资源,不得不说,是迄今为止用来改进面试式算法问题最有效的工具。 LeetCode收录了许多互联网公司的算法题目,被称为刷题神器。它扫遍全...

    HuangWeiAI
  • ​LeetCode刷题实战16: 最接近的三数之和

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就...

    程序IT圈
  • ​LeetCode刷题实战16: 最接近的三数之和

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就...

    程序IT圈
  • 更接近的三数之和

    给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数,使得它们的和与 target 最接近。返回这三个数的和。假...

    木子星兮
  • 【LeetCode】16. 最接近的三数之和

    给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数,使得它们的和与 target 最接近。返回这三个数的和。假...

    韩旭051

扫码关注云+社区

领取腾讯云代金券