leetcode的第16道题,关于数组的一道算法题,在下的代码不能通过测试集,但是在下实在不知错误出在哪里,特来此处,请帮帮在下。
问题:
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).
在下的代码:
class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
int size = nums.size(); //取数组大小 方便判断
if (size<3)
return 0;
std::sort(nums.begin(), nums.end()); //排序 方便后续操作
int gap = INT_MAX; //存储与target相差的值
for(int i=0;i<size-2;++i){ //因为是三数之和 所以在循环到size-2
int front = i+1; //第二个加数
int back = size-1; //第三个家数
while(front<back){ //在for循环内进行第二次循环 以此判断在第一个加数确定的情况下的各种情况
int sum = nums[i]+nums[front]+nums[back]; //取三数之和
if(abs(gap)>abs(sum-target)) //判断相差值的大小 如果相差值变大 则gap不变 若相差值变小 则gap更新
gap=sum-target;
if (gap == 0)
return sum; //相等 返回和
else if(gap>0)
back--; //较大 让第三个加数变小
else
front++; //较小 让第二个加数变大
}
while(i<size-2&&nums[i+1]==nums[i]) //该循环用于跳过不必要的元素
i++;
}
return (gap+target);
}
};
你的代码会漏算一些case,按照轮询写的话,你试试
int threeSumClosest(vector<int>& nums, int target)
{
int size = nums.size(); //取数组大小 方便判断
if (size < 3)
return 0;
std::sort(nums.begin(), nums.end()); //排序 方便后续操作
int gap = INT_MAX; //存储与target相差的值
int iSum = 0;
int iPreSum = iSum;
bool bSetPreSum = false;
bool bFind = false;
int index, index2, index3;
for (int i = 0; i < size - 2; i++)
{
if (bFind)
{
break;
}
for (int i2 = i + 1; i2 < size - 1; i2++)
{
if (bFind)
{
break;
}
for (int i3 = i2 + 1; i3 < size; i3++)
{
iSum = nums[i] + nums[i2] + nums[i3];
if (!bSetPreSum)
{
iPreSum = iSum;
index = i;
index2 = i2;
index3 = i3;
bSetPreSum = true;
}
if (iSum == target)
{
bFind = true;
iPreSum = iSum;
index = i;
index2 = i2;
index3 = i3;
break;
}
else if (abs(iSum - target) < abs(iPreSum - target))
{
iPreSum = iSum;
index = i;
index2 = i2;
index3 = i3;
}
}
}
}
bFind = true;
printf("closest sum = %d + %d + %d = %d\n", nums[index], nums[index2], nums[index3], (iPreSum));
return iSum;
}