- 标签:数组、双指针、排序
- 难度:中等
描述:给定一个整数数组
要求:从
说明:
-
$3 \le nums.length \le 1000$ 。 -
$-1000 \le nums[i] \le 1000$ 。 -
$-10^4 \le target \le 10^4$ 。
示例:
- 示例 1:
输入:nums = [-1,2,1,-4], target = 1
输出:2
解释:与 target 最接近的和是 2 (-1 + 2 + 1 = 2)。
- 示例 2:
输入:nums = [0,0,0], target = 1
输出:0
直接暴力枚举三个数的时间复杂度是
- 先对数组进行从小到大排序,使用
$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] \ge target$ ,则说明$right$ 太大了,应该将$right$ 左移,然后继续判断。
- 如果
- 当
$left == right$ 时,区间搜索完毕,继续遍历$nums[i + 1]$ 。 - 最后输出
$ans$ 。
这种思路使用了两重循环,其中内层循环当
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
-
时间复杂度:$O(n^2)$,其中
$n$ 为数组中元素的个数。 -
空间复杂度:$O(\log n)$,排序需要
$\log n$ 的栈空间。