最接近的三数之和
难度:
标签:
题目描述
给你一个长度为 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
提示：
3 <= nums.length <= 1000-1000 <= nums[i] <= 1000-104 <= target <= 104
代码结果
运行时间: 120 ms, 内存: 14.9 MB
/*
* 思路：
* 1. 使用Java Stream对数组进行排序。
* 2. 使用双指针法计算最接近目标值的三元组和。
*/
import java.util.Arrays;
public class Solution {
public int threeSumClosest(int[] nums, int target) {
nums = Arrays.stream(nums).sorted().toArray();
int closestSum = nums[0] + nums[1] + nums[2];
for (int i = 0; i < nums.length - 2; i++) {
int left = i + 1;
int right = nums.length - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum == target) {
return sum;
}
if (Math.abs(sum - target) < Math.abs(closestSum - target)) {
closestSum = sum;
}
if (sum < target) {
left++;
} else {
right--;
}
}
}
return closestSum;
}
}解释
方法:
该解法采用了双指针的思路，首先将数组排序，然后固定一个元素，利用双指针在剩余的元素中寻找与目标值最接近的两个数。具体步骤如下：
1. 对数组进行排序。
2. 遍历数组，对于每个元素nums[k]，在剩余的元素中使用双指针i和j分别指向nums[k+1]和数组末尾。
3. 计算当前三个数的和s，如果s与目标值target的差的绝对值小于当前答案ans与target差的绝对值，则更新ans为s。
4. 如果s等于target，直接返回s；如果s大于target，则将右指针j向左移动；如果s小于target，则将左指针i向右移动。
5. 重复步骤3-4，直到左右指针相遇。
6. 返回最接近目标值的和ans。
时间复杂度:
O(n^2)
空间复杂度:
O(1)
代码细节讲解
🦆
为什么在解法中先对数组进行排序？这对双指针策略有什么帮助？
▷🦆
在双指针策略中，如果当前三个数的和等于目标值，为什么可以立即返回这个和？
▷🦆
你是如何确定将数组的前三个数的和作为初始答案ans的？是否有其他选择策略？
▷🦆
在调整左右指针时，移动条件是基于和与目标值的比较，这样的操作如何保证最终找到最接近目标的和？
▷🦆
算法的时间复杂度是O(n^2)，能否通过优化进一步降低复杂度？
▷🦆
如果在实际使用中输入数组很短或包含重复元素，这种情况下算法的表现如何？
▷相关问题
三数之和
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请
你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例 1：
输入：nums = [-1,0,1,2,-1,-4] 输出：[[-1,-1,2],[-1,0,1]] 解释： nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。 nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。 nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。 不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。 注意，输出的顺序和三元组的顺序并不重要。
示例 2：
输入：nums = [0,1,1] 输出：[] 解释：唯一可能的三元组和不为 0 。
示例 3：
输入：nums = [0,0,0] 输出：[[0,0,0]] 解释：唯一可能的三元组和为 0 。
提示：
3 <= nums.length <= 3000-105 <= nums[i] <= 105