LeetCode 16. 最接近的三数之和

题目:

---

给定一个包括 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.