【每日一题】LeetCode - 最接近的三数之和

LeetCode 的「最接近的三数之和」问题要求我们从给定整数数组中找到三个数的和，使它最接近目标值。适合初学者的原因在于它结合了双指针、排序等基本技巧，为大家理解基本的算法和数据结构提供了一个很好的机会。

如果你不知道什么是双指针可以参考我之前发的博客，或者直接看我数据结构的博客专栏

• 【数据结构】双指针算法：理论与实战

一、题目介绍

给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。

返回这三个数的和。

假定每组输入只存在恰好一个解。

这道题与上一题很类似，如果你没看过上一题强烈建议务必去看一下

• 【每日一题】LeetCode - 三数之和

示例 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。

二、解题思路

1. 排序：首先将数组排序，这有助于后续通过双指针更有效地缩小范围。
2. 遍历 + 双指针：遍历每个元素作为三元组的第一个元素，然后利用双指针来找到另外两个数。
3. 求最接近的和：通过计算当前和与目标的差距，不断更新最接近的和。

三、代码实现

以下是代码实现，带有详细注释：

class Solution {public: int threeSumClosest(vector<int>& nums, int target) { int ans = 0x7fffffff, sum = 0; sort(nums.begin(), nums.end()); for(int i = 0; i < nums.size(); i ++) { if(i > 0 && nums[i] == nums[i - 1]) continue; int left = i + 1, right = nums.size() - 1; while(left < right) { int currentSum = nums[i] + nums[left] + nums[right]; int res = currentSum - target; if(abs(res) < abs(ans)) {  ans = res;  sum = currentSum; } if(res < 0) left++; else right--; } } return sum; }};

四、详细代码解释

1. 排序：首先对数组进行升序排序，使得我们可以使用双指针的方式进行查找。排序的时间复杂度为 O(n log n)。
2. 遍历数组：代码中我们用一个 for 循环来遍历数组，遍历的目的是固定三元组中的第一个元素 nums[i]。
3. 双指针操作：对于固定的 nums[i]，用两个指针 left 和 right 分别指向剩余部分的首尾，计算三数之和并与目标值比较。
   • 更新最接近的和：如果当前和比记录的最接近值更接近目标值，则更新答案。
   • 移动指针：若当前和小于目标值，说明我们需要一个更大的值来接近目标，因此 left++；反之则 right--。

五、时间复杂度和空间复杂度分析

• 时间复杂度：

  • 排序的复杂度为 O(n log n)。
  • 外层遍历和内层双指针的复杂度为 O(n^2)。
  • 整体时间复杂度为 O(n^2)。

• 空间复杂度：

  • 使用了常数级的额外空间来保存变量，因此空间复杂度为 O(1)。

六、其他解法比较

• 暴力解法：可以使用三重循环来检查每个可能的三数之和，但这种方法的时间复杂度为 O(n^3)，在数据量大时效率较低。

暴力解法代码实现

暴力解法通过三重循环来枚举数组中所有可能的三数组合，计算它们的和并与目标值比较，从而找到最接近的和。

class Solution {public: int threeSumClosest(vector<int>& nums, int target) { int closestSum = 0x7fffffff; int minDiff = 0x7fffffff; for (int i = 0; i < nums.size() - 2; ++i) { for (int j = i + 1; j < nums.size() - 1; ++j) { for (int k = j + 1; k < nums.size(); ++k) {  int currentSum = nums[i] + nums[j] + nums[k];  int diff = abs(currentSum - target);  if (diff < minDiff) { minDiff = diff; closestSum = currentSum;  } } } } return closestSum; }};

暴力解法的分析

• 时间复杂度：暴力解法的时间复杂度为 O(n^3)，因为需要三重循环来枚举所有三数组合。这种复杂度在 n 较大时会导致性能瓶颈。

• 空间复杂度：该解法仅使用了常数额外空间，因此空间复杂度为 O(1)。

• 双指针优化：相比暴力解法，双指针法在保证准确性的同时减少了计算次数，更加高效。