本文主要是介绍[LeetCode]16.3Sum Closest，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
【题目】
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).
【题意】
给定n个整数的数组S，寻找S中三个整数，使得总和最接近给定的目标。
返回三个整数的总和。
你可以假设每个输入将有一个确切的解决方案。
【分析】
题目思路和上题差不多。
先排序，二分查找来左右逼近。
对于a + b + c ，对a规定一个数值时，采用二分查找b，c使Sum= a + b + c 最接近target。
a可以取数组S中任何一个数值，使得有多个Sum，CurClosest = abs(target - Sum)求Min( CurClosest ),即最接近的那个。
【代码】
/*********************************
* 日期：2014-01-18
* 作者：SJF0115
* 题号: 16.3Sum Closest
* 来源：http://oj.leetcode.com/problems/3sum-closest/
* 结果：AC
* 来源：LeetCode
* 总结：
**********************************/
#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <LIMITS.H>
using namespace std;class Solution {
public:int threeSumClosest(vector<int> &num, int target) {int i,j,result,start,end,Sum,CurClosest,MinClosest = INT_MAX;int Len = num.size();//排序sort(num.begin(),num.end());for(i = 0;i < Len-2;i++){start = i + 1;end = Len - 1;//二分查找while(start < end){//a + b + cSum = num[i] + num[start] + num[end];//接近度CurClosest = abs(target - Sum);//更新最接近的Targetif(CurClosest < MinClosest){MinClosest = CurClosest;result = Sum;}//相等 -> 目标(唯一一个解)if(target == Sum){return Sum;}//大于 -> 当前值小需要增大else if(target > Sum){start ++;}//小于 -> 当前值大需要减小else{end --;}}//while}//forreturn result;}
};
int main() {int result;Solution solution;vector<int> vec;vec.push_back(-1);vec.push_back(2);vec.push_back(1);vec.push_back(-4);result = solution.threeSumClosest(vec,-4);printf("Target:%d\n",result);return 0;
}
这篇关于[LeetCode]16.3Sum Closest的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
