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).
The code is slight different from the 3 sum problem, just change the if condition, the key point is to use the abs() function to get the distances between the target and the output value.
The source code:
class Solution { public: int threeSumClosest(vector<int> &num, int target) { // Start typing your C/C++ solution below // DO NOT write int main() function int res; vector<int>::iterator it1,it2,it3,iend; sort(num.begin(),num.end()); if(num.size()>=3){ res = num.at(0)+num.at(1)+num.at(2); iend = num.end(); it1 = num.begin(); bool f1 = false; for ( ;it1!=iend-2;++it1){ if(f1 && *it1==*(it1-1)) {continue;} f1 = true; bool f2 = false; bool f3 = false; it3 = iend-1; it2 = it1+1; while (it2!=it3){ if(f3 && *it3==*(it3+1)) { it3 = it3 -1 ;continue;} if(f2 && *it2==*(it2-1)) { it2 = it2 +1 ;continue;} if (*it1 + *it2 + *it3==target){ res = target; return res; } if (*it1 + *it2 + *it3 >target){ if (abs(target - (*it1 + *it2 + *it3)) < abs(target-res)){ res = *it1 + *it2 + *it3; } it3=it3-1; f3 = true; }else{ if (abs(target - (*it1 + *it2 + *it3)) < abs(target-res)){ res = *it1 + *it2 + *it3; } it2=it2+1; f2 = true; } } } } return res; } };
Hi, can we reduce the lines of code anyhow? I mean can we think of a shorter and efficient code like this?
ReplyDelete