欢迎来到李耶的频道【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);letclosestnums[0]nums[1]nums[2];for(leti0;inums.length-2;i){letlefti1;letrightnums.length-1;while(leftright){constsumnums[i]nums[left]nums[right];// 更新最接近的和if(Math.abs(sum-target)Math.abs(closest-target)){closestsum;}if(sumtarget){returntarget;}elseif(sumtarget){right--;}else{left;}}}returnclosest;}时间复杂度 / 空间复杂度O(n²) / O(log n) 或 O(n)排序 O(n log n)双指针遍历 O(n²)总体 O(n²)空间复杂度取决于排序算法优势最推荐与三数之和解法一脉相承是面试中的标准写法解法对比解法时间复杂度空间复杂度推荐指数排序 双指针O(n²)O(log n)⭐⭐⭐⭐⭐扩展题三数之和找出所有和为 0 的三元组要求不重复。四数之和找出所有和为 target 的四元组。最接近的四数之和给定数组和目标值找出和最接近 target 的一个四元组。“只有人们的社会实践才是人们对于外界认识的真理性的标准。” —— 毛泽东关注李耶每天一道面试题一起卷起来