【LeetCode】16.最接近的三数之和

欢迎来到李耶的频道【LeetCode面试题】。

最接近的三数之和

16.最接近的三数之和

题目

给定一个包括n个整数的数组nums和一个目标值target。找出nums中的三个整数，使得它们的和与target最接近。返回这三个数的和。假定每组输入只存在唯一答案。

输入：nums = [-1,2,1,-4], target = 1 输出：2 解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2)

输入：nums = [0,0,0], target = 1 输出：0

输入：nums = [0,0,0], target = 0 输出：0

解法一：排序 + 双指针（标准解）

思路：先对数组排序，然后固定一个数nums[i]，用双指针left和right在i右侧区间内寻找两数之和。每次计算三数之和与target的差值，记录差值最小的和。根据sum与target的大小关系移动双指针。

functionthreeSumClosest(nums,target){nums.sort((a,b)=>a-b);letclosest=nums[0]+nums[1]+nums[2];for(leti=0;i<nums.length-2;i++){letleft=i+1;letright=nums.length-1;while(left<right){constsum=nums[i]+nums[left]+nums[right];// 更新最接近的和if(Math.abs(sum-target)<Math.abs(closest-target)){closest=sum;}if(sum===target){returntarget;}elseif(sum>target){right--;}else{left++;}}}returnclosest;}

• 时间复杂度 / 空间复杂度：O(n²) / O(log n) 或 O(n)
  • 排序 O(n log n)，双指针遍历 O(n²)，总体 O(n²)
  • 空间复杂度取决于排序算法
• 优势：最推荐，与三数之和解法一脉相承，是面试中的标准写法

解法对比

扩展题

1. 三数之和：找出所有和为 0 的三元组，要求不重复。
2. 四数之和：找出所有和为 target 的四元组。
3. 最接近的四数之和：给定数组和目标值，找出和最接近 target 的一个四元组。

“只有人们的社会实践，才是人们对于外界认识的真理性的标准。” —— 毛泽东

关注李耶，每天一道面试题，一起卷起来 🔥