【每日一题】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。

二、解题思路

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

三、代码实现

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

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;}
};

四、详细代码解释

排序：首先对数组进行升序排序，使得我们可以使用双指针的方式进行查找。排序的时间复杂度为 O(n log n)。
遍历数组：代码中我们用一个 for 循环来遍历数组，遍历的目的是固定三元组中的第一个元素 nums[i]。
双指针操作：对于固定的 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;}
};