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

• 2020 年 2 月 16 日
• 笔记

木又同学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++版本