- 标签:数组、双指针、排序
- 难度:中等
给你一个整数数组 nums
和 一个目标值 target
。
要求:从 nums
中选出三个整数,使它们的和与 target
最接近。返回这三个数的和。假定每组输入只存在恰好一个解。
直接暴力枚举三个数的时间复杂度是
- 先对数组进行从小到大排序,使用
ans
记录最接近的三数之和。 - 遍历数组,对于数组元素
nums[i]
,使用两个指针left
、right
。left
指向第0
个元素位置,right
指向第i - 1
个元素位置。 - 计算
nums[i]
、nums[left]
、nums[right]
的和与target
的差值,将其与ans
与target
的差值作比较。如果差值小,则更新ans
。- 如果
nums[i] + nums[left] + nums[right] < target
,则说明left
小了,应该将left
右移,继续查找。 - 如果
nums[i] + nums[left] + nums[right] >= target
,则说明right
太大了,应该将right
左移,然后继续判断。
- 如果
- 当
left == right
时,区间搜索完毕,继续遍历nums[i + 1]
。 - 最后输出
ans
。
这种思路使用了两重循环,其中内层循环当 left == right
时循环结束,时间复杂度为
class Solution:
def threeSumClosest(self, nums: List[int], target: int) -> int:
nums.sort()
res = float('inf')
size = len(nums)
for i in range(2, size):
left = 0
right = i - 1
while left < right:
total = nums[left] + nums[right] + nums[i]
if abs(total - target) < abs(res - target):
res = total
if total < target:
left += 1
else:
right -= 1
return res