三数之和

默认分类 | 2018-01-03 20:55:52 | 100次阅读 | 0评

三数之和为所要的数,或三数之和为最接近所要的数。

vector<int> threeSumClosest(vector<int> &num,int target)
{
    int len=num.size();
    int min=INT_MAX;
    vector<int> result;
    for(int i=0;i<len;i++)
    {
        int start=i+1,end=len-1;
        while(start<end)
        {
              if(num[start]+num[end]==target-num[i])
              {
	    min=0;
	    result.push_back(num[i]);
	    result.push_back(num[start]);
	    result.push_back(num[end]);
	    result.push_back(1);
	    break;
               }
	else if(num[start]+num[end]<target-num[i]) 
	{
                if(min>abs(num[i]+num[start]+num[end]-target))
	{
	min=abs(num[i]+num[start]+num[end]-target);
                 result.push_back(num[i]);
	result.push_back(num[start]);
	result.push_back(num[end]);
	result.push_back(0);
	}
	start++;
	}
	else 
	{
                if(min>abs(num[i]+num[start]+num[end]-target))
	{
	min=abs(num[i]+num[start]+num[end]-target);
                 result.push_back(num[i]);
	result.push_back(num[start]);
	result.push_back(num[end]);
	result.push_back(0);
	}
	end--;
	}
	if(result[result.size()-1]==1) break;
       	}   
	while(i<len && num[i]==num[i+1]) i++;
	}
	return result;
}

 

博友评论,共0条
浏览190次
阅读排行
最新评论