【Leetcode】【4Sum】【四数之和】【C++】
标签：递归 if语句 没有 整数 ast break bre 方法 nbsp
- 题目：给定一个整数数组nums和一个目标值target，判断是否存在四个数a,b,c,d，使得a+b+c+d=target？找出所有满足条件且不重复的四元组
- 示例：
-
nums = [1, 0, -1, 0, -2, 2]，和 target = 0
-
满足要求的四元组集合为： [ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2] ]
- 说明： 注意找出的四元组不重合，即没有相同的四元组；且四元组按从小到大的顺序输出。
-
思路1：对nums数组排序，然后两个for循环遍历，获取两个数组元素，在剩余元素中找出两个数，这两个数与之前两个数组元素的和为targe。（注意，可能剩余元素中满足要求的两个数不止一对，如target=9，for循环获取到的两个数是1,2 那么就要在剩余元素中找出和为6的两个数，如果剩余元素为2,3,3,4，那么满足要求的有[2,4] 和[3,3]）（另外，还要注意两个for循环遍历的两个元素不能有相同，这样也会造成重复）
- 代码：
-
class Solution {
public:
vectorint> > fourSum(vectorint>& nums, int target) {
vectorint> > res;
sort(nums.begin(),nums.end());
int len=nums.size();
for(int i=0; i)
{
if(i!=0 && nums[i]==nums[i-1])
continue; //判断nums[i]是否和上次一个（如果有的话）相等
for(int j=i+1; j)
{
if(j!=(i+1) && nums[j]==nums[j-1])
{
continue;//作用类似于上面的if语句，判断是否重复
}
vectorint> >sum2;
int temTarg= target-nums[i]-nums[j];
int left=j+1,right=len-1;
int lastleftval=-1,lastrightval=-1;
bool flag=false;
while(leftright)
{
if(left ==i || left==j)
{
left++;
continue;
}
if(right==i || right==j)
{
right--;
continue;
}
if((nums[left]+nums[right])==temTarg)//此处，可能有不止一对满足条件的结果，故找到后不能简单得用break语句跳出循环
{
if(flag==true && nums[left]==lastleftval && nums[right]==lastrightval)
{
left++;
right--;
continue;
}
flag=true;
lastleftval=nums[left];
lastrightval=nums[right];
vectorint>subsum2;
subsum2.push_back(nums[left]);
subsum2.push_back(nums[right]);
sum2.push_back(subsum2);
left++;
right--;
}
else if((nums[left]+nums[right])>temTarg)
{
right--;
}
else
{
left++;
}
}
int lensum2=sum2.size();
for(int k=0; k)
{
vectorint>temp;
temp.push_back(nums[i]);
temp.push_back(nums[j]);
temp.push_back(sum2[k][0]);
temp.push_back(sum2[k][1]);
res.push_back(temp);
}
}
}
return res;
}
};
-
思路2：递归解决（使用于求k个数之和的情况，这种方法更普遍），将求k数之和转换为求k-1数之和，直到k=2
- 代码：
-
class Solution {
vectorint> > kSum(vectorint>& nums, int start, int k, int target)
{
vectorint> > res;
int len=nums.size();
if(k==2)
{
int left=start,right=len-1;
int lastleftval=-1,lastrightval=-1;
bool flag=false;// flag=false表示还未满足条件的元祖
while(leftright)
{
if((nums[left]+nums[right])>target)
right--;
else if((nums[left]+nums[right])target)
left++;
else
{
if(flag==true && lastleftval==nums[left] && lastrightval==nums[right])
{
left++;
right--;
continue;
}
flag=true;
lastleftval=nums[left];
lastrightval=nums[right];
vectorint> subres;
subres.push_back(nums[left]);
subres.push_back(nums[right]);
res.push_back(subres);
left++;
right--;
}
}
return res;
}
int lastval=-1;
for(int i=start; i)
{
if(i!=start && nums[i]==nums[i-1])
continue;
vectorint> > subres= kSum(nums, i+1, k-1, target-nums[i]);
int sublen=subres.size();
for(int j=0; j)
{
vectorint>temp;
temp.push_back(nums[i]);
for(int j1=0; j11; j1++)
temp.push_back(subres[j][j1]);
res.push_back(temp);
}
}
return res;
}
public:
vectorint> > fourSum(vectorint>& nums, int target) {
vectorint> > res;
int len=nums.size();
if(len==0)
return res;
sort(nums.begin(),nums.end());
return kSum(nums,0,4,target);
}
};
【Leetcode】【4Sum】【四数之和】【C++】
标签：递归 if语句 没有 整数 ast break bre 方法 nbsp
原文地址：https://www.cnblogs.com/dreamer123/p/9681648.html
评论