javascript实现给一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数使它们的和与 target 最接近。
以下是JavaScript实现代码:
function threeSumClosest(nums, target) {
nums.sort((a, b) => a - b); // 先将数组排序
let closestSum = nums[0] + nums[1] + nums[2]; // 初始化最接近的和
for (let i = 0; i < nums.length - 2; i++) {
let left = i + 1, right = nums.length - 1;
while (left < right) {
const sum = nums[i] + nums[left] + nums[right];
if (Math.abs(sum - target) < Math.abs(closestSum - target)) { // 更新最接近的和
closestSum = sum;
}
if (sum === target) { // 如果三个数的和刚好等于目标值,直接返回
return target;
} else if (sum < target) { // 如果三个数的和小于目标值,将左指针右移
left++;
} else { // 如果三个数的和大于目标值,将右指针左移
right--;
}
}
}
return closestSum;
}
这个算法的时间复杂度为O(n^2),其中n为数组的长度。排序的时间复杂度为O(nlogn),外层循环的时间复杂度为O(n),内层循环的时间复杂度为O(n),所以总的时间复杂度为O(n^2)。算法的空间复杂度为O(1),因为只使用了常数个变量来保存最接近的和和三个数的和。
原文地址: https://www.cveoy.top/t/topic/0rr 著作权归作者所有。请勿转载和采集!