本文給出了＃15：3sum - 避免重複

Question

FYI問題陳述：

給定n個整數中S，從而使A + B + C = 0的數組S，在那裏元件A，B，C？查找數組中所有唯一的三元組，它們的總和爲零。

注意：這套解決方案必須不包含重複的三胞胎。

例如，給定陣列S = [ - 1，0，1，2，-1，-4]

的溶液組爲：[[ - 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; 
} 

我得到的，

你的回答：[[-1，-1,2]

不匹配

預期的答案： [[-1，-1,2]，[ - 1,0,1]

我很想添加[-1,0,1]，但它應該只添加到矢量中一次。

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？