给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数,使它们的和与 target 最接近。 返回这三个数的和。 假定每组输入只存在恰好一个解。 示例 1: 输入:nums = [-1,2,1,-4], target = 1 输出:2 解释:与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。 示例 2: 输入:nums = [0,0,0], target = 1 输出:0
时间: 2024-04-10 08:26:48 浏览: 144
可以使用双指针的方法来解决这个问题。首先对数组进行排序,然后依次固定一个数,使用双指针在剩下的数中寻找与目标值最接近的两个数。
具体步骤如下:
1. 将数组排序。
2. 初始化一个变量diff,用于记录当前最接近的和与目标值的差距。初始化为一个较大的值。
3. 遍历数组,对于每个固定的数nums[i],使用双指针left和right分别指向i+1和数组末尾。
4. 在每一轮循环中,计算当前三个数的和sum,如果sum与target的差距比diff小,则更新diff为sum与target的差距,并更新结果res为sum。
5. 根据sum与target的大小关系,移动left或right指针来逼近目标值。如果sum大于target,则将right指针向左移动;如果sum小于target,则将left指针向右移动。
6. 循环结束后,返回结果res。
以下是使用Python实现的代码:
```python
def threeSumClosest(nums, target):
nums.sort()
diff = float('inf')
res = 0
for i in range(len(nums)-2):
left = i + 1
right = len(nums) - 1
while left < right:
sum = nums[i] + nums[left] + nums[right]
if abs(sum - target) < diff:
diff = abs(sum - target)
res = sum
if sum > target:
right -= 1
elif sum < target:
left += 1
else:
return target
return res
```
对于示例1,调用`threeSumClosest([-1,2,1,-4], 1)`,会返回2。
对于示例2,调用`threeSumClosest([0,0,0], 1)`,会返回0。
阅读全文