美文网首页
leetcode16. 最接近的三数之和 python实现

leetcode16. 最接近的三数之和 python实现

作者: vvblack4 | 来源:发表于2020-02-22 19:32 被阅读0次

题目:

leetcode16题目描述

解法:

  1. 先对数组从小到大排序。
  2. 最外层遍历整个数组,再设置两个双指针,当三数之和sum大于target时,右指针向左移动一位;当三数之和sum小于target时,左指针向右移动一位。
  3. 设置一个diff是三数之和和target的差的绝对值,如果diff比当前的mindiff小,则替换mindiff。

具体代码如下:

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        nums.sort()
        res = 0
        mindiff = 100000

        for i in range(len(nums)):
            left = i+1
            right = len(nums)-1
            while left<right:
                sum = nums[left]+nums[right]+nums[i]
                diff = abs(sum - target)
                if diff < mindiff:
                    mindiff = diff
                    res = sum
                if sum == target:
                    return sum
                elif sum>target:
                    right -= 1
                else:
                    left += 1
        return res

相关文章

网友评论

      本文标题:leetcode16. 最接近的三数之和 python实现

      本文链接:https://www.haomeiwen.com/subject/pzhrqhtx.html