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

发布时间：2020-12-20 09:55:11 所属栏目：Python 来源：网络整理

导读：题目描述; 给定一个包括?n 个整数的数组?nums?和一个目标值?target。找出?nums?中的三个整数，使得它们的和与?target?最接近。返回这三个数的和。假定每组输入只存在唯一答案。例如，给定数组 nums = [-1，2，1，-4],和 target = 1. 与 target 最接近的三

题目描述;

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

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

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

解题：

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:
                     target
                if abs(res-target) > abs(cur-target):
                    第一次判断时总是成立的，因为此时res是无穷大
                    res = cur
                if cur > target:当前值太大了，将右指针左移
                    r -= 1
                else: 当前值太小了，将左指针右移
                    l += 1
        return res

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

结果：

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!