三数之和姊妹题——LeetCode题目16：最接近的三数之和
三数之和姊妹题——LeetCode题目16：最接近的三数之和
二环宇少
发布于 2020-08-13 15:30:43
发布于 2020-08-13 15:30:43
原题描述
+
给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。
示例
输入：nums=[-1, 2, 1, 4], target=1
输出：2
解释：与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).
原题链接：https://leetcode-cn.com/problems/3sum-closest
思路解析
+
这道题我建议你和下面这道题一起看，因为它们的思路几乎一模一样。下面这道题如果会做，那么本题对你来说会变得相当容易。 LeetCode题目15：三数之和
相对于上面这道题来说，本题容易的地方在于不需要考虑去重，这会让双指针的移动更简单，我再讲一下这里面涉及到的两种情况。
假设我们对数组按升序排序，并以第 处的数字为基础，来寻找它的另外两个同伴，那么在这个有序数组上，我们一定可以通过移动处于 右侧的两个边界指针 和 来实现不断逼近target的目的。
情况1——当nums[i]+nums[L]+nums[R] > target时，我们需要左移 来缩小三数之和，这样才有可能找到与target更接近的值。
情况2——当nums[i]+nums[L]+nums[R] <= target时，我们需要右移 来增加三数之和。
好了，现在可以写代码了。
在LeetCode中不会有重复的题目，但是思路接近可以类比的题目确很多。编程和做数学题一样，需要大量的练习才能强化自己的sense和逻辑性。
复杂度分析
+
- 时间复杂度：
- 空间复杂度：
C++参考代码
+
class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
int sum = 0;
if (nums.size() < 2) {
for (int i = 0; i < nums.size(); ++i) sum += nums[i];
return sum;
}
sort(nums.begin(), nums.end());
int min_dist = INT_MAX;
for (int i = 0; i < nums.size() - 2; ++i) {
int l = i + 1;
int r = nums.size() - 1;
while (l < r) {
int curr_sum = nums[i] + nums[l] + nums[r];
if (curr_sum < target) {
if (target - curr_sum < min_dist) {
min_dist = target - curr_sum;
sum = curr_sum;
}
++l;
} else {
if (curr_sum - target < min_dist) {
min_dist = curr_sum - target;
sum = curr_sum;
}
--r;
}
}
}
return sum;
}
};本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2020-05-31，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读