處理重複數組元素

Question

我在處理數組中的重複元素時遇到了麻煩。例如，在尋找一個陣列，其總和爲規定值以內的所有整數對的問題，這是我實現：

vector<pair<int, int>> find_all_pairs_with_sum(int data[], int length, int sum) 
{ 
    assert(data && length>1); 

    vector<pair<int, int>> res; 

    sort(data, data+length); 

    int first = 0; 
    int last = length - 1; 
    while (first < last) 
    { 
     int s = data[first] + data[last]; 
     if (s == sum) 
     { 
      res.push_back(make_pair(data[first], data[last])); 

      ++first; 
      --last; 
     } 
     else 
     { 
      if (s < sum) 
       ++first; 
      else 
       --last; 
     } 
    } 

    return res; 
} 

當數組包含重複的元素將出現問題。例如，當

int data[] = {3, 4, 3, 4}; 
int sum = 7; 

該方案只會給兩個對(3,4) (3,4)。然而，在這種情況下，正確的答案應該是四對(3,4) (3,4) (3,4) (3,4)（如4 = 2x2）。如何修改代碼以正確處理這種情況（希望仍在O(n logn)）？在更新first和last時，似乎應該在if (s==sum)範圍內進行更改，但我無法做到正確。

請注意：我知道另一種方法，可以通過使用hash table記錄每個元素的出現來正確處理此問題。請建議如何解決此問題而不使用hash table。

Answer 1

你的數組被歸類爲

Index: 0 1 2 3 
Element: 3 3 4 4 

當你找到的總和，你增加first和減少last，所以每對只加一次，而不是兩次。此外，以任何速度向內步進總是會阻止你獲得1-3和0-2（按指數）。你可以做一個初步的傳球找到重複，並利用這些信息來正確地添加對：

vector<pair<int, int>> find_all_pairs_with_sum(int data[], int length, int sum) 
{ 
    assert(data && length>1); 

    vector<pair<int, int>> res; 
    int i; 

    sort(data, data+length); 

    // there is more than one way to skin this cat... 
    vector<pair<int, int>> vettedData; 
    for(i = 0; i < length; i++) { 
     if(i == 0 || vettedData[vettedData.size() - 1].first != data[i]) 
      vettedData.push_back(make_pair(data[i], 1)); 
     else 
      vettedData[vettedData.size() - 1].second++; 
    } 

    int first = 0; 
    int last = vettedData.size() - 1; 
    while (first < last) 
    { 
     int s = vettedData[first].first + vettedData[last].first; 
     if (s == sum) 
     { 
      int iterations = vettedData[first].second * vettedData[last].second; 
      for(i = 0; i < iterations; i++) 
       res.push_back(make_pair(vettedData[first].first, vettedData[last].first)); 

      ++first; 
      --last; 
     } 
     else 
     { 
      if (s < sum) 
       ++first; 
      else 
       --last; 
     } 
    } 

    return res; 
}