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

2020-02-22  本文已影响0人  vvblack4

题目:

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
上一篇 下一篇

猜你喜欢

热点阅读