题目描述
给出含有n个整数的数组s，找出s中和加起来的和最接近给定的目标值的三个整数。返回这三个整数的和。你可以假设每个输入都只有唯一解。 例如，给定的整数 S = {-10 20 10 -40}, 目标值 = 10. 最接近目标值的和为 20. (-10 + 20 + 10 = 20). 示例1 输入 [0,0,0],1 复制 0
思路分析：本题和求三数之和十分类似，即给出一个数组和目标值，问数组中是否存在三数之和等于目标值，解题思路是类似的。
首先将数组进行一个简单排序，定义三个指针，当前元素指针顺序向后遍历；每次遍历时，下一个元素指针和最后一个元素指针分别指向i+1和num.size（）-1的位置，当小于target时start++，当大于target时end–，当start==end时结束一次遍历；在遍历过程中，用result存储最小差值的数值，tmp存储临时计算值，和target比较谁的差更小，然后更新result的数据； #include <algorithm> class Solution { public: /** * * @param num int整型vector * @param target int整型 * @return int整型 */ int threeSumClosest(vector<int>& num, int target) { // write code here int result = num[0] + num[1] + num[num.size() - 1]; sort(num.begin(),num.end()); for (int i = 0; i < num.size() - 2; i++) { int start = i + 1, end = num.size() - 1; while (start < end) { int sum = num[i] + num[start] + num[end]; if (sum > target) end--; else start++; if (abs(sum - target) < abs(result - target)) result = sum; } } return result; } };补充：此处直接使用了库函数sort排序，下面附一个快速排序的版本。快速排序的原理讲解请点击此处。
#include <algorithm> class Solution { public: /** * * @param num int整型vector * @param target int整型 * @return int整型 */ void quickSort(vector<int>& num, int low, int high) { if (low < high) { // 找寻基准数据的正确索引 int index = getIndex(num, low, high); // 进行迭代对index之前和之后的数组进行相同的操作使整个数组变成有序 //quickSort(arr, 0, index - 1); 之前的版本，这有很大的性能问题，谢谢大家的建议 quickSort(num, low, index - 1); quickSort(num, index + 1, high); } } int getIndex(vector<int>& num, int low, int high) { // 基准数据 int tmp = num[low]; while (low < high) { // 当队尾的元素大于等于基准数据时,向前挪动high指针 while (low < high && num[high] >= tmp) { high--; } // 如果队尾元素小于tmp了,需要将其赋值给low num[low] = num[high]; // 当队首元素小于等于tmp时,向后挪动low指针 while (low < high && num[low] <= tmp) { low++; } // 当队首元素大于tmp时,需要将其赋值给high num[high] = num[low]; } // 跳出循环时low和high相等,此时的low或high就是tmp的正确索引位置 // 由原理部分可以很清楚的知道low位置的值并不是tmp,所以需要将tmp赋值给arr[low] num[low] = tmp; return low; // 返回tmp的正确位置 } int threeSumClosest(vector<int>& num, int target) { // write code here int result = num[0] + num[1] + num[num.size() - 1]; //sort(num.begin(),num.end()); quickSort(num,0,num.size()-1); for (int i = 0; i < num.size() - 2; i++) { int start = i + 1, end = num.size() - 1; while (start < end) { int sum = num[i] + num[start] + num[end]; if (sum > target) end--; else start++; if (abs(sum - target) < abs(result - target)) result = sum; } } return result; } };