题目描述:
给你一个长度为 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 最接近的和是 0(0 + 0 + 0 = 0)。
解题思路:
本题目因为要计算三个数,如果靠暴力枚举的话需要3层遍历,时间复杂度会到 O(n3),这是不推荐的,直接说结果吧,需要采用双指针算法,描述如下:
双指针算法
- 先让数组有序,也就是需要先对数组进行排序
- 然后每次固定一个元素,再去寻找另外两个元素,也就是双指针
双指针法的代码实现:
1.使用sort方法对数组进行排序
2.假设结果值result是一个无穷大Infinity;
3.每次遍历的过程中设置两个指针,分别是 left = i + 1、right = nums.length - 1。
4.检查 sum = nums[i] + nums[left] + nums[right]与 target 的距离,如果该距离比之前保存的 result 与 target 的距离更小,就更新 result。
5.然后就是移动双指针。
6.如果 sum 的值比 target 大,那么我们让 right--,因为数组是有序的,right --会使得下一次的 sum 更小,也就更接近 target 的值
7.同理,如果 sum 的值 target 小,那么我们让 left++。·
8.left++ 和 right-- 的界限是 left < right,一是保证:left和right索引对应的不能是同一个值(题目要求left, right是2个值) 二是如果 left > right, left的索引会越界(导致while循环赋值比较逻辑出错)
9.如果sum != target,则会返回result (每次遍历:会根据Math.abs绝对值比较选择最小)
function threeSumClosest(nums, target) {nums.sort((a, b) => a - b) // 1.先对nums递增排序let result = Infinity; // 2.假设结果值是一个无穷大(假想值)for (let i = 0; i < nums.length; i++) { // 3.遍历numslet left = i + 1; // 第二个值设置为下一个索引(左指针:代表较小值)let right = nums.length - 1; // 第三个值设置为最后一个索引(右指针:代表较大值)while (left < right) { // 4. 此处保证:1)left和right索引对应的不能是同一个值(题目要求left, right是2个值) 2) right索引对应值必须比left索引对应值大let sum = nums[i] + nums[left] + nums[right] // 5.三个值求和if (Math.abs(sum - target) < Math.abs(result - target)) { // 6.sum-target可能是一个负值(负值数字越小反而值越大),所以取绝对值比较result = sum // 7.如果Math.abs(sum - target) < Math.abs(result - target),则说明sum离目标值target距离越小,也就是更接近目标值,所以此时将最接近sum值更新给result}if (sum < target) { // 如果当前求和的sum值 < 目标值target, 说明离目标值距离还不够接近,让左指针index++,往中间靠拢,值会变大left++;} else if (sum > target) { // 如果当前求和的sum值 > 目标值target, 说明离目标值距离超过了,让右指针index--,往中间靠拢,值会变小right--;} else {return sum; // 如果当前求和的sum值 === 目标值target,则达成要求,直接返回sum}}}return result; // 如果求和sum值没有等于目标值target,则返回最接近的值};const nums = [-1, 2, 1, -4];const target = 1;const closestNum = threeSumClosest(nums, target);console.log(closestNum); // 输出结果为 2
图解实现:
1.排序
2. for循环遍历判断