825
[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
* 來源：https://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 + c
Sum = num[i] + num[start] + num[end];
//接近度
CurClosest = abs(target - Sum);
//更新最接近的Target
if(CurClosest < MinClosest){
MinClosest = CurClosest;
result = Sum;
}
//相等 -> 目標(唯一一個解)
if(target == Sum){
return Sum;
}
//大於 -> 當前值小需要增大
else if(target > Sum){
start ++;
}
//小於 -> 當前值大需要減小
else{
end --;
}
}//while
}//for
return 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;
}
最後更新：2017-04-03 12:54:38