wordpress迁站到阿里云,哪个网站可以做付费推广,嘉兴做网站优化哪家好,制作相册音乐相册模板原题地址#xff1a;. - 力扣#xff08;LeetCode#xff09; 题目描述 给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数#xff0c;使它们的和与 target 最接近。 返回这三个数的和。 假定每组输入只存在恰好一个解。 示例 1#xf… 原题地址. - 力扣LeetCode 题目描述 给你一个长度为 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
解释与 target 最接近的和是 00 0 0 0。提示 3 nums.length 1000-1000 nums[i] 1000-104 target 104 解题思路 排序首先对数组进行排序以便可以使用双指针法来寻找三个数的和。遍历使用一个循环固定第一个数 nums[i]然后使用双指针 slow 和 fast 来查找另外两个数使得三数之和最接近给定的目标值。计算差值每次计算三数之和并更新与目标值的最小差值及最近的和。如果找到完全匹配的和直接返回。移动指针根据三数之和与目标值的大小关系移动指针 如果和小于目标值移动左指针以增加和。如果和大于目标值移动右指针以减少和 代码实现
class Solution {public int threeSumClosest(int[] nums, int target) {// 输入有效性检查if (nums null || nums.length 3) {return 0; // 由于没有足够的数返回 0}int minDifference Integer.MAX_VALUE; // 最小差值初始化为最大值int closestSum 0; // 最近和初始化为 0// 排序数组Arrays.sort(nums);// 遍历数组固定第一个数for (int i 0; i nums.length - 2; i) {int slow i 1; // 左指针int fast nums.length - 1; // 右指针// 使用双指针查找最接近的三数之和while (slow fast) {int sum nums[i] nums[slow] nums[fast]; // 计算三数之和// 更新最小差值和最近和if (Math.abs(sum - target) minDifference) {minDifference Math.abs(sum - target);closestSum sum;}// 根据三数之和与目标值的比较移动指针if (sum target) {slow; // 和小于目标移动左指针} else if (sum target) {fast--; // 和大于目标移动右指针} else {return sum; // 找到完全匹配直接返回}}}return closestSum; // 返回最接近的和}
}复杂度分析 时间复杂度O(n²)外层循环遍历每个元素内层双指针查找组合。数组排序的时间复杂度为 O(n log n)整体复杂度为 O(n²)。空间复杂度O(1)只使用了常量级别的额外空间不考虑结果值的空间。
