注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

HT·生活

123

 
 
 

日志

 
 

ex16 3sum closest  

2015-05-21 22:02:59|  分类: leetcode |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
3 sum题目的一个变种

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).
以前是相等的时候就是结果,这个题目的话,就是一直循环,直到找到最接近的一个值,原理一样,就是把findtwosum的函数改动一下。见c代码

/*
*这题是3sum问题的升级版,几乎和3sum问题一样,只是在查找twosum的
* 函数里面需要做一些变动
*/
class Solution {
public:
int min = INT_MAX;
int res;
bool flag;
int threeSumClosest(vector<int>& nums, int target) {
if (nums.size() < 3)
return 0;
sort(nums.begin(), nums.end()); //先用快排排序

int len = nums.size();
for (int i = 0; i < len - 2; i++)
{
//因为只可能遍历到倒数第二个
if (i>0 && nums[i] == nums[i - 1])
continue; //避免出现重复的结果
findTwoSum(nums, i + 1, len - 1, nums[i],target);
}
return res;

}
void findTwoSum(vector<int>nums, int begin, int end, int current,int target)
{
int left = begin;
int right = end;
int temp,result;
while (left < right)
{
temp = current + nums[left] + nums[right];
result = temp; //保存结果
temp = temp - target;

if (temp < 0) //求绝对值
{
temp = -1 * temp;
flag = false;
left++;
}
else
{
right--;
flag = true;
}
if (temp < min)
{
min = temp;
res = result;
}
}
}
};


  评论这张
 
阅读(8)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017