intellij idea汉化 Nginx配置 微服务 laravel multithreading curl text enums interface proxy get swiper vuejs视频教程 jquery去掉空格 docker的安全特性有哪些 mser算法 quartz配置 新手学c还是java oracle行转列函数 flutter优缺点 pyhton中异常和模块 mysql时间戳转换日期 python中time python图形界面开发 java入门级教程 java语言基础教程 java注释 java怎么写接口 java生成文件 win10长期服务版 gtx1030 神龙kms h370主板 stl2stp 快点蛆虫成就单刷 小米手环充电多久 显示器面板类型 今日头条邀请码 idea导出jar包 毕业证件照
当前位置: 首页 > 学习教程  > python

【Leetcode】16. 最接近的三数之和(3Sum Closest)

2021/2/7 10:54:36 文章标签: 测试文章如有侵权请发送至邮箱809451989@qq.com投诉后文章立即删除

No16. 最接近的三数之和 题目 给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数,使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。 示例 输入:nums [-1,2,1,-4], target 1输出&…

No16. 最接近的三数之和

题目

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

示例

  • 输入:nums = [-1,2,1,-4], target = 1
  • 输出:2
  • 解释:与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。

提示

  • 3 <= nums.length <= 10^3
  • -10^3 <= nums[i] <= 10^3
  • -10^4 <= target <= 10^4

解题代码(Python3)

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        nums.sort()
        #初始化
        res = 10**4+1
        #用来判断最接近target的数
        def judgeClose(a,b):
            return a if abs(a-target) < abs(b-target) else b
        #子函数 相当于最接近target-value的2个数
        def returnCloseValue(left,right,value):
            #用res来存最接近target的值
            res = num + nums[left] + nums[right]
            while left < right:
                tmp = num + nums[left] + nums[right]
                if tmp > target:
                    right -= 1
                elif tmp < target:
                    left += 1
                #如果等于target 直接返回target
                else:
                    return target
                res = judgeClose(res,tmp)
            return res
        for i, num in enumerate(nums[:-2]):
            #这里大于0是防止对第一个位置判断有误 如果重复则continue
            if i > 0 and num == nums[i-1]:
                continue
            temp = returnCloseValue(i + 1,len(nums) - 1,num)
            if temp == target:
                return target
            else:
                res = judgeClose(res,temp)
        return res

思路:

这题与15题很类似,求三个数a+b+c,使得其和与target最接近,可以先将整个nums进行排序,然后最外层循环固定为a,简化成求另外两个数和target-a的最小差值

复杂度分析:

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

运行结果:

在这里插入图片描述


本文链接: http://www.dtmao.cc/news_show_2000235.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?