美文网首页
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