欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

LeetCode 16. 最接近的三数之和

程序员文章站 2022-04-11 15:45:05
...

题目:


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

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

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


思路:

Target 固定,三个数的组合的和最接近target即返回,答案唯一。

所以,首先思路是排序,然后找三个数相加的减去target 取绝对值比较,最小的那组返回value即可。

方法一:

这和上一题思路很像,先来一个笨方法,去找每一个三数相加组合去比较,很显然超时....

class Solution(object):
    def threeSumClosest(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        nums.sort() 
        length = len(nums)
        res = {}
        for i in xrange(length):
            j = i+1
            while j<=length-2 :
                k = j
                while k <= length-2:
                    k +=1
                    res[abs(nums[i]+nums[j]+nums[k]-target)] = nums[i]+nums[j]+nums[k]
                j +=1   
        return res[min(list(res.keys()))] 

方法二:

如何减少循环次数呢,两个while的地方肯定有一部分是可以舍去的,因为有做排列动作。结合上题三数之和方法二的思路,采用双指针去做,这样就不用2个while 去遍历了,一个while即可,处理思想和方法一一样,取差值绝对值返回最小值value,但是时间省了不少。

class Solution(object):
    def threeSumClosest(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        nums.sort() 
        length = len(nums)
        res = nums[0] + nums[1] + nums[2]
        for i in xrange(length):
            left, right = i + 1 , length - 1
            while left < right:
                res_sum = nums[i] + nums[left] + nums[right]
                if abs(res_sum-target) < abs(res - target):
                    res = res_sum
                if res_sum > target:
                    right -=1
                elif res_sum < target:
                    left +=1
                else:
                    return res_sum
        return res

执行用时 :68 ms, 在所有 Python 提交中击败了72.01%的用户

内存消耗 :12.6 MB, 在所有 Python 提交中击败了12.50%的用户

Knowledge, like candlelight, can illuminate a person and countless people.