力扣每日一题:16.最接近的三数之和 双指针解法

简介: 力扣每日一题:16.最接近的三数之和 双指针解法

16.最接近的三数之和


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

难度:中等


题目:

给定一个包括n 个整数的数组nums和 一个目标值target。找出nums中的三个整数,

使得它们的和与target最接近。返回这三个数的和。假定每组输入只存在唯一答案。

提示:

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


示例:

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


分析

这道题的题目比较短,获取最接近target目标值的三数之和。

首先拿到这种题,我们要先看下提示中的取值范围,3 <= nums.length <= 10^3条件标志着。

不会出现不足三个数字的异常场景,但10^3 如果三层for循环10^9必然会超时,暴力解法不通。

那么,下来就需要考虑优化方案:

  1. 二分查找 or hash表?
  • 二分查找和hash表只针对单个数字,那势必我们需要先双层循环再二分,10^6一样会超时。
  1. 缩减条件
  • 既然三个数字我们有些无从下手,那么先使用一层for循环,减少一个数字的筛选再来考虑是否就简单了一些。
  • 减少一个数字后,我们的题目变成了查找数组中某两个最接近target - num1,是不就变成了一道基础题。
  1. 实现方案
  • 我们先将nums排序
  • 设置返回值ret,初始为float('inf')无穷大
  • 开始for i in range(len(nums))循环
  • 设置left = i + 1,right = length - 1
  • tmp = nums[left] + nums[rigth]
  • 比较 ret和tmp+nums[i],哪个更接近target,并赋值给ret
  • 如果tmp = target - nums[i],表示找到了三个数等于target直接返回target
  • 如果tmp > target - nums[i],我们将right -= 1
  • 如果tmp < target - nums[i],我们将left -= 1
    最终,即可获取结果。


解题:

class Solution:
    def threeSumClosest(self, nums, target):
        ret = float('inf')
        nums.sort()
        length = len(nums)
        for i in range(length - 2):
            left = i + 1
            right = length - 1
            while left < right:
                tmp = nums[i] + nums[left] + nums[right]
                ret = tmp if abs(tmp - target) < abs(ret - target) else ret
                if tmp == target:
                    return target
                if tmp > target:
                    right -= 1
                else:
                    left += 1
        return ret




相关文章
|
3月前
|
算法
LeetCode第16题最接近的三数之和
该文章介绍了 LeetCode 第 16 题最接近的三数之和的解法,与第 15 题类似,通过双指针法减少循环次数,根据差值的绝对值来更新最接近的和,并总结了双指针可减少循环次数的要点。
|
3月前
|
算法 Java
LeetCode经典算法题:矩阵中省份数量经典题目+三角形最大周长java多种解法详解
LeetCode经典算法题:矩阵中省份数量经典题目+三角形最大周长java多种解法详解
51 6
|
3月前
|
人工智能 算法 Java
LeetCode经典算法题:井字游戏+优势洗牌+Dota2参议院java解法
LeetCode经典算法题:井字游戏+优势洗牌+Dota2参议院java解法
50 1
|
3月前
|
存储 算法 Java
LeetCode经典算法题:预测赢家+香槟塔java解法
LeetCode经典算法题:预测赢家+香槟塔java解法
60 1
|
3月前
|
Python
【Leetcode刷题Python】16. 最接近的三数之和
解决LeetCode "最接近的三数之和" 问题的Python实现,通过排序和双指针法,记录并更新与目标值最接近的三数之和。
36 1
|
3月前
|
算法 Java
LeetCode初级算法题:环形链表+排列硬币+合并两个有序数组java解法
LeetCode初级算法题:环形链表+排列硬币+合并两个有序数组java解法
54 0
|
3月前
|
存储 算法 Java
LeetCode初级算法题:两数之和+斐波拉契数列多种java解法
LeetCode初级算法题:两数之和+斐波拉契数列多种java解法
39 0
|
5月前
|
索引
力扣每日一题 6/17 枚举+双指针
力扣每日一题 6/17 枚举+双指针
33 1
|
5月前
|
存储 算法 数据可视化
【模拟面试问答】深入解析力扣163题:缺失的区间(线性扫描与双指针法详解)
【模拟面试问答】深入解析力扣163题:缺失的区间(线性扫描与双指针法详解)