本文共 3218 字，大约阅读时间需要 10 分钟。
#include#include #include #include #include using namespace std;/*问题:Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution. For example, given array S = {-1 2 1 -4}, and target = 1. The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).分析：这个是找到三个数的和要最接近给定值。与之前三数和不同的是这里肯定要修改判定条件。要维护一个最接近给定值的数值，每当 有新的最接近的数值的时候，就更新。 暴力破解：一个三层循环，分别对每个数字遍历，计算三数和的结果，取最接近的，时间复杂度为O(n^3) 两数和思想：如果选中一个数a作为给定值，那么作为目标的两数和-a最接近的部分，所以似乎没有思路。 简化问题：如果是一个数组求两数和最接近指定数值，求这个两数和t，该怎么做？ 设两个下标分别为low,high,数组为A,sum=A[low] + A[high]，设定两数和sum和target之间的差值diff=INT_MAX, sum > t:则sum可能是结果集，假设此时low++,只会使得sum更大，所以不对，因此是high--，如果|sum-target| < diff,则diff=|sum-differget|,记录两数和sum sum < t:则sum可能是结果集，此时应该low++，同时判定是否需要更新结果集 sum = t:则sum就是结果集，直接输出 因为此题是最接近，因此答案应该是一个，如果有多个也输出一个 经过上述分析：此时三数和最接近也可以用上述二数和最接近的思路来做，时间复杂度仍为O(n^2)输入:4(数组元素个数) 1(三数和的目标值)-1 2 1 -46 0-2 -1 0 1 1 2输出:20关键：1 简化问题：如果是一个数组求两数和最接近指定数值，求这个两数和t，该怎么做？ 设两个下标分别为low,high,数组为A,sum=A[low] + A[high]，设定两数和sum和target之间的差值diff=INT_MAX, sum > t:则sum可能是结果集，假设此时low++,只会使得sum更大，所以不对，因此是high--，如果|sum-target| < diff,则diff=|sum-differget|,记录两数和sum sum < t:则sum可能是结果集，此时应该low++，同时判定是否需要更新结果集 sum = t:则sum就是结果集，直接输出 因为此题是最接近，因此答案应该是一个，如果有多个也输出一个 经过上述分析：此时三数和最接近也可以用上述二数和最接近的思路来做，时间复杂度仍为O(n^2)*/class Solution {public: //计算两数之和，结果可能多个。如何去重？已经有一个数被使用了，这个数不能出现在求两数之和的结果中，遇到该下标直接跳过 int twoSum(vector & nums , int value , int selectIndex) { if(nums.empty()) { return 0; } int sum; int size = nums.size(); int low = 0; int high = size - 1; int minDiff = INT_MAX; int diff; int resultSum; while(low < high) { //如果左边的数字等于已经选择的数字，则low++ if(selectIndex == low) { low++; } else if(selectIndex == high) { high--; } //如果发现不满足，则退出 if(low >= high) { break; } //如果两数之和小于目标值，则令low++;两数之和大于目标值，high--;如果两数之和等于目标值，则low++,high-- sum = nums.at(low) + nums.at(high); diff = abs(sum - value); //如果遇到更接近给定值的两数和，记录结果 if(diff < minDiff) { resultSum = sum; minDiff = diff; } if(sum < value) { low++; } else if(sum > value) { high--; } //找到了，说明找到最接近的，直接输出 else { break; low++; high--; } } return resultSum; } int threeSumClosest(vector & nums, int target) { //数据为空，返回为0 if(nums.empty()) { return 0; } //先排序 sort(nums.begin(), nums.end()); int size = nums.size(); int realTarget; int sum; int resultSum; int diff; int minDiff = INT_MAX; int threeSumResult; for(int i = 0 ; i < size ; i++) { realTarget = target - nums.at(i); sum = twoSum(nums , realTarget , i); threeSumResult = sum + nums.at(i); diff = abs(threeSumResult - target); if(diff < minDiff) { minDiff = diff; resultSum = threeSumResult; } } return resultSum; }};void process(){ int num; vector nums; vector< vector > results; int value; int target; while(cin >> num >> target) { nums.clear(); for(int i = 0 ; i < num ; i++) { cin >> value; nums.push_back(value); } Solution solution; int result = solution.threeSumClosest(nums , target); cout << result << endl; }}int main(int argc , char* argv[]){ process(); getchar(); return 0;}
转载地址：http://nhofn.baihongyu.com/