大家好,又见面了,我是全栈君,今天给大家准备了Idea注册码。
Given an array S of n integers, are there elements a, b, c,
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)
这是求四个数的和的问题。能够和前面三个数和的问题一样转化成两个数和的问题。即先固定第一个数。再依据第一个数固定第二个数,然后就是求两数和的问题了。数组里面的元素可能会有反复元素,所以须要注意消除反复的推断。时间复杂度是O(N^3)。
runtime:192ms
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<vector<int>> result;
if(nums.size()<4)
return result;
sort(nums.begin(),nums.end());
vector<int>::iterator iter1=nums.begin();
vector<int>::iterator iter2=iter1+1;
//最外层第一个指针遍历
for(;iter1!=nums.end()-3;iter1++)
{
//固定第一个指针后第二个指针遍历
for(iter2=iter1+1;iter2!=nums.end()-2;iter2++)
{
//内层两个指针从两个方向遍历,这是经典的求两个数的和的问题
int base=*iter1+*iter2;
vector<int>::iterator iter3=iter2+1;
vector<int>::iterator iter4=nums.end()-1;
while(iter3<iter4)
{
if((*iter3+*iter4+base)<target)
{
iter3++;
}
else if((*iter3+*iter4+base)>target)
{
iter4--;
}
else
{
//这里须要注意vector中push_back和用下标訪问的差别,用小标訪问时相似于数组,所以tmp初始化时须要指定vector的大小,可是用push_back时不要指定大小。否则小心push_back是在你指定大小的vector后加入元素
vector<int> tmp;
tmp.push_back(*iter1);
tmp.push_back(*iter2);
tmp.push_back(*iter3);
tmp.push_back(*iter4);
result.push_back(tmp);
//这是推断是否有反复的方式,假设下一指针依旧小于iter4而且下一个指针指向的值与当前值同样。iter3须要加1
while((iter3+1)<iter4 && *(iter3)==*(iter3+1)) iter3++;
while(iter3<(iter4-1)&& *(iter4)==*(iter4-1)) iter4--;
//推断完毕后还须要将iter3加1或iter4减一以继续查寻下一个和为常数的组合
iter3++;
}
}
//对于iter2也须要推断是否存在反复元素问题
while(((iter2+1)!=(nums.end()-2))&&(*(iter2)==*(iter2+1))) iter2++;
}
//同理对于ier1也是如此
while(((iter1+1)!=(nums.end()-3))&&(*(iter1)==*(iter1+1))) iter1++;
}
return result;
}
};
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/116673.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...