leetcode:3sum closet
テーマ:1つの配列と与えられた目標値を与えて、配列の中で3つの要素を探し出すことを要求して、この3つの要素の和は最も目標値に接近して、もちろん最も良いことに等しいです.
3 sumの方法で、判定条件を少し修正します.
3 sumの方法で、判定条件を少し修正します.
int twoSum(vector<int> &num, int start, int target)
{
if(num.size() < 3 || start >= num.size())
return -target;
int head = start;
int tail = num.size() - 1;
int result = -target;
int erro = 0x7fffffff;
while (head < tail)
{
int sum = num[head] + num[tail];
if(sum == target)
{
result = target;
return target;
}
else if(sum < target){
do
{
++head;
} while (head < tail && num[head] == num[head - 1]);
}
else
{
do
{
--tail;
} while (tail > head && num[tail] == num[tail + 1]);
}
int curerro = abs(sum - target);
if(curerro < erro)
{
result = sum;
erro = curerro;
}
}
return result;
}
int threeSumClosest(vector<int> &num, int target) {
const int len = num.size();
if(len < 3)
return 0;
sort(num.begin(), num.end());
int closet = -target;
int erro = 0x7fffffff;
for (int i = 0; i < len - 2; ++i)
{
int thisloop = twoSum(num, i + 1, target - num[i]);
if(thisloop == target - num[i])
return target;
int cur_erro = abs(thisloop + num[i] - target);
if(cur_erro < erro)
{
closet = thisloop + num[i];
erro = cur_erro;
}
while(i + 1 < len && num[i + 1] == num[i])
++i;
}
return closet;
}