[LeetCode]16. 最接近的三数之和(3Sum Closest)

题目描述

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

例如,给定数组 nums = [-1,2,1,-4], 和 target = 1.

与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).

解题思路

  1. 排序。复杂度 $O(n\log n)$;
  2. 遍历数组。
    1. 当前数字索引为 i
    2. 遍历当前数之后的所有数字:start=i+1end=length-1,计算这三个数字的和,若等于目标值,则直接返回;小于目标值,则 start 后移;大于目标值,则 end 前移。

代码

Python 3.6

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
def threeSumClosest(self, nums: List[int], target: int) -> int:
nums.sort()
res = sum(nums[:3])
for i in range(len(nums)):
cur = nums[i]
start = i + 1
end = len(nums) - 1
while start < end:
cur = nums[i] + nums[start] + nums[end]
if abs(cur - target) < abs(res - target):
res = cur
if cur == target:
return cur
if cur < target:
start += 1
else:
end -= 1
return res

执行用时 : 188 ms
内存消耗 : 13.9 MB

参考

https://leetcode-cn.com/problems/3sum-closest/solution/hua-jie-suan-fa-16-zui-jie-jin-de-san-shu-zhi-he-b