前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >【python-leetcode15-双指针】最接近的三数之和

【python-leetcode15-双指针】最接近的三数之和

作者头像
西西嘛呦
发布2020-08-26 16:03:07
4250
发布2020-08-26 16:03:07
举报
文章被收录于专栏:数据分析与挖掘

题目描述;

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

例如,给定数组 nums = [-1,2,1,-4], 和 target = 1.

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

解题:

代码语言:javascript
复制
class Solution:
    def threeSumClosest(self, nums,target):
        #如果数组为空或者长度小于3,返回空
        if not nums or len(nums) < 3:
            return None
        #先排序
        nums.sort()
        #表示res是无穷大
        res = float("inf")
        #从左往右遍历数组
        for i in range(len(nums)):
            #对于重复的值,只需要计算一次即可
            if i > 0 and nums[i] == nums[i-1]:
                continue
            #左指针
            l = i + 1
            #右指针
            r = len(nums) - 1
            #核心就是不断增大左指针指向的值和缩小右指针指向的值
            #使得三个数的和尽量靠近target
            while l < r:
                # 记录当前三个数的和
                cur = nums[i] + nums[l] + nums[r]
                #如果找到等于target的三个数,直接返回即可
                if cur == target:
                    return target
                if abs(res-target) > abs(cur-target):
                    #第一次判断时总是成立的,因为此时res是无穷大
                    res = cur
                if cur > target:#当前值太大了,将右指针左移
                    r -= 1
                else: #当前值太小了,将左指针右移
                    l += 1
        return res

其中很关键的一步就是如何确定初始值,即要让res首先是无穷大。

结果:

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2020-02-16 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档