原题描述
+
给定一个包括 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：三数之和
二环宇少，公众号：互联网西门二少LeetCode题目15：三数之和
相对于上面这道题来说，本题容易的地方在于不需要考虑去重，这会让双指针的移动更简单，我再讲一下这里面涉及到的两种情况。
假设我们对数组按升序排序，并以第
情况1——当nums[i]+nums[L]+nums[R] > 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;
}
};
讲技术，也谈风月，更关注程序员的生活状况，欢迎联系二少投稿你感兴趣的话题。
文章转载自西门宇少，如果涉嫌侵权，请发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。
