16. 最接近的三数之和[medium]

https://leetcode-cn.com/problems/3sum-closest/

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

示例：

输入：nums = [-1,2,1,-4], target = 1 输出：2 解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。

提示：

3 <= nums.length <= 10^3
-10^3 <= nums[i] <= 10^3
-10^4 <= target <= 10^4

通过次数104,904 提交次数237,514

First Try

2020-06-05

与3 sum差不多的思路，在右边的两个指针不断往中间靠拢的过程中，需要不停的与已有的最小值进行比较更新，双指针其实每次都是遍历了一遍的，这样看来其实也不算高效。对于暴力解法的O(n^3),使用双指针可以降到O(n^2),这就是双指针夹逼的贡献了。

class Solution(object):
    def threeSumClosest(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        nums = sorted(nums)
        rv = [nums[0], nums[1], nums[2]]
        for i in range(len(nums) - 2):
            mid = i + 1
            right = len(nums) - 1
            while mid < right:
                curr = [nums[i], nums[mid], nums[right]]
                if abs(sum(curr) - target) < abs(sum(rv) - target):
                    rv = curr
                res = sum(curr) - target
                if res == 0:
                    break
                elif res < 0:
                    mid += 1
                else:
                    right -= 1
        return sum(rv)

执行用时 :492 ms, 在所有 Python 提交中击败了6.64%的用户
内存消耗 :12.8 MB, 在所有 Python 提交中击败了12.50%的用户

16. 最接近的三数之和[medium]​

First Try​

16. 最接近的三数之和[medium]

First Try