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

HT·生活

123

 
 
 

日志

 
 

ex18 4sum  

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

  下载LOFTER 我的照片书  |
这一题,比3sum多了一层循环而已,ksum的问题,复杂度是n^(k-1),我是这么理解的

Given an array S of n integers, are there elements abc, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note:

  • Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a ≤ b ≤ c ≤ d)
  • The solution set must not contain duplicate quadruplets.

    For example, given array S = {1 0 -1 0 -2 2}, and target = 0.

    A solution set is:
    (-1,  0, 0, 1)
    (-2, -1, 1, 2)
    (-2,  0, 0, 2)
在3sum外层再加一层循环,就是4sum这道题的答案了。

class Solution {
public:
vector<vector<int>> res;
vector<vector<int>> fourSum(vector<int>& nums, int target) {
if (nums.size() < 4)
return res;
sort(nums.begin(), nums.end()); //先用快排排序

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

}
return res;
}
void findTwoSum(vector<int>nums, int begin, int end, int target,int a,int b)
{
int left = begin;
int right = end;
while (left < right)
{
if ((a+b+nums[left] + nums[right] - target) == 0)
{
vector<int> temp;
temp.push_back(a);
temp.push_back(b);
temp.push_back(nums[left]);
temp.push_back(nums[right]);
res.push_back(temp);

//下面就是要过滤掉重复的nums[left]和nums[right]
while ((left < right) && (nums[left] == nums[left + 1]))
left++;
while ((left < right) && (nums[right] == nums[right - 1]))
right--;

left++; //不要退出,因为后面可能还有
right--;
}
else
{
if ((a+b+nums[left] + nums[right]) > target)
{
right--;
}
else
{
left++;
}
}
}
}
};


参考,这个里面有各种sum总结

http://tech-wonderland.net/blog/summary-of-ksum-problems.html
  评论这张
 
阅读(4)| 评论(0)
推荐 转载

历史上的今天

评论

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

页脚

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