【leetcode刷题】20T11-最接近的三数之和

木又同学2020年第11篇解题报告

leetcode第16题：最接近的三数之和

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

【题目】

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

例如，给定数组 nums = [-1，2，1，-4], 和 target = 1. 与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).

【思路】

暴力解法，三层循环，得到所有的三数相加和，进而得到距离最近三数和，时间复杂度为O(n^3)。

可以对数组排序后，对于每个元素，使用两数之和等于target的类似方法得到三个数距离target较近的和。

【代码】

python版本

class Solution(object):
    def threeSumClosest(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        nums.sort()
        res = sys.maxsize
        for i, n in enumerate(nums):
            j, k = i + 1, len(nums) - 1
            while j < k:
                tmp = nums[i] + nums[j] + nums[k]
                if tmp == target:
                    return target
                # 距离target更小
                if abs(tmp - target) < abs(res - target):
                    res = tmp
                if tmp > target:
                    k -= 1
                else:
                    j += 1
        return res           

复制

C++版本           

复制