仅供引用问题陈述:
Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Note: The solution set must not contain duplicate triplets.
For example, given array S = [-1, 0, 1, 2, -1, -4]
A solution set is: [ [-1, 0, 1], [-1, -1, 2] ]
下面是我的算法,它按预期合理地工作,但我无法弄清楚如何防止重复。我已经评论了我试图跟踪重复集(三胞胎)的部分。
vector<vector<int>> threeSum(vector<int>& nums)
{
vector< vector<int> > res;
int a,b,c,start,end;
int preva=0,prevb=0,prevc=0; //variables to track elements of
//triplet pushed into result
//vector the previous run.
sort(nums.begin(),nums.end());
int n=nums.size();
for(int i=0; i<=n-3;i++){
a = nums[i];
start = i+1;
end = n-1;
while (start < end){
b = nums[start];
c = nums[end];
if (a+b+c == 0)
{
if ((a!=preva)&&(b!=prevb)&&(c!=prevc)) //check if duplicate
res.push_back({a,b,c}); //add triplet
//to res vector if not
//present.
end = end - 1;
preva=a;
prevb=b;
prevc=c;
}
else if (a+b+c > 0)
end = end - 1;
else
start = start + 1;
}
}
return res;
}
我明白了,
Your answer: [[-1,-1,2]]
不匹配
Expected answer: [[-1,-1,2],[-1,0,1]]
我完全没有添加 [-1,0,1],而应该只将它添加到 vector 中一次。
最佳答案
考虑以下 if
语句中的条件表达式:
if ((a!=preva)&&(b!=prevb)&&(c!=prevc)) //check if duplicate
如果 a,b,c
都不匹配 preva,prevb,prevc
,这将仅推送结果;在 [-1,0,1]
的情况下,我们最终有 a = -1
匹配来自 的
。此外,这只会检查紧接在前的解决方案。preva = -1
[-1,-1,2]
相反,您应该确定一种与顺序无关的方式来存储这些结果,并让容器本身处理重复项——可能是 std::set
而不是 vector
?
关于c++ - 力扣#15 : 3sum -- avoiding duplicate,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/38909591/