【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++版本