最接近的三数之和【LC16】
给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。
返回这三个数的和。
假定每组输入只存在恰好一个解。
x数之和总结，可以看看其他类似题目
难道明天是LC259？
2023/1/14
- 思路：
- 搜索三数之和的过程与LC15相同：首先对数组进行排序，然后遍历数组，在确定
nums[i]的情况下，在数组nums[i+1,n-1]中使双指针法（前后指针），确定另外两个元素，判断这三个元素之和sum与target的大小：
- 如果sum>target，左移左指针，使
sum减小 - 如果sum<target，右移右指针，使
sum增大 - 如果sum==target，添加三元组至结果集
- 不同之处为更新结果的条件变为如果
sum更接近target那么更新sum。如果sum==target，那么可以直接返回target。本题不去重也不影响结果 - 本题只需要找到最接近的和，因此去重不是必须的
- 实现
// 2023/7/10 class Solution { public int threeSumClosest(int[] nums, int target) { Arrays.sort(nums); int n = nums.length ; int res = Integer.MAX_VALUE; for (int i = 0; i < n - 2; i++){ int l = i + 1, r = n - 1; if (i > 0 && nums[i] == nums[i - 1]){ continue; } while (l < r){ int sum = nums[i] + nums[l] + nums[r]; if (Math.abs(sum - target) < Math.abs(res - target)){ res = sum; } if (sum == target){ return target; }else if(sum > target){ r--; }else{ l++; } } } return res; } }
复杂度
- 时间复杂度：O(nlogn+n2)，其中 n是数组的长度。排序所需的时间复杂度一般为O(nlogn)，查找三元组的时间复杂度为O(n2)，因此时间复杂度为O(n2)
- 空间复杂度：O(1)
