处理重复数组元素

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; 
}