c++ - 力扣#15 : 3sum -- avoiding duplicate

Question

仅供引用问题陈述:

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 中一次。

Answer 1

考虑以下 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?