本文主要是介绍LeetCode 16 3Sum Closest，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：
给出数组s和目标target，要求从中选出3个数字，使其相加的和最接近target。
思路：
x sum系列的题目，在这里做一个总结。
最经典的情况为2 sum问题，即给出s和target找出s[i] + s[j] = target。
可以使用枚举s[i]判断target - s[i]是否在s中出现且与s[i]不同的O(nlogn)方法，用map或排序后二分查找的方式均可。
也可以使用夹逼搜索的方法，即先将s排序，指针l指向s头，r指向s尾，若s[l] + s[r] < target则++l否则--r。
这种方法的思想类似于枚举s[l]，判断target - s[l]是否等于s[r]。如果s[r] > target - s[l]，那么r应该指向更小的值，否则说明这个s[l]找不到合适的s[r]，这时就枚举下一个s[l]。
排序O(nlogn)，夹逼搜索O(n)，也就是说2 sum问题可以O(nlogn)解决。
x sum问题可以通过枚举1个数字转化成x-1 sum问题，这样不断转化直到2 sum为止。
本题求closest，那么只需要记录一下当前搜索的数字的和sum与target的差距即可。
代码：
//
// Created by 房籽呈 on 2017/1/24.
//class Solution {
public:int threeSumClosest(vector<int> &nums, int target) {sort(nums.begin(), nums.end());int ans = nums[0] + nums[1] + nums[2];for (int i = 0; i < nums.size(); ++i) {for (int l = i + 1, r = nums.size() - 1; l < r;) {int sum = nums[i] + nums[l] + nums[r];if (abs(sum - target) < abs(ans - target)) {ans = sum;if (ans == target) {return target;}}if (sum < target) {++l;} else {--r;}}}return ans;}
};这篇关于LeetCode 16 3Sum Closest的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
