求解二和问题(含指数)的最有效算法

Question

问题陈述给出了一个数组和一个给定的和"T"，找到数组中元素的所有对索引，这些索引加在一起达到T.额外的要求/约束：

• 索引从0
• 开始索引必须首先以较低的索引显示(Ex: 24，30而不是30，24)
• 索引必须按升序显示(Ex:如果我们发现(1,3)，(0,2)和(5,8)输出必须是(0,2) (1,3) (5，8)
• ，数组中可以有重复的元素，这些元素也必须被认为是

。

下面是我在C++中的代码，我使用了使用unordered_set的哈希表方法

void Twosum(vector <int> res, int T){
    
    int temp; int ti = -1;
    unordered_set<int> s;
    vector <int> res2 = res;                  //Just a copy of the input vector
    vector <tuple<int, int>> indices;         //Result to be output
    
    for (int i = 0; i < (int)res.size(); i++){
        temp = T - res[i];

        if (s.find(temp) != s.end()){
            
            while(ti < (int)res.size()){     //While loop for finding all the instances of temp in the array, 
                                             //not part of the original hash-table algorithm, something I added
                
                ti = find(res2.begin(), res2.end(), temp) - res2.begin();  
                                              //Here find() takes O(n) time which is an issue
                
                res2[ti] = lim;               //To remove that instance of temp so that new instances 
                                              //can be found in the while loop, here lim = 10^9
                
                if(i <= ti) indices.push_back(make_tuple(i, ti));
                else indices.push_back(make_tuple(ti, i)); 
            }
        }
        s.insert(res[i]);
    }
    
    if(ti == -1)
        {cout<<"-1 -1";                        //if no indices were found
         return;}
    
    sort(indices.begin(), indices.end());       //sorting since unordered_set stores elements randomly
    for(int i=0; i<(int)indices.size(); i++)
        cout<<get<0>(indices[i])<<" "<<get<1>(indices[i])<<endl;
}

这有多个问题：

• 首先指出，虽然循环不按预期工作，但它显示了SIGABRT错误(free(): invalid pointer)。ti索引也在某种程度上超出了向量界，尽管我在while ti中签入了find()函数在O(n)时间内工作，这使总体复杂性增加到O(n^2)，这导致我的程序在执行过程中超时。但是，这个函数是必需的，因为我们必须输出indices.
• Lastly --当数组中有许多重复的元素时，这个unordered-set实现似乎不能工作(因为sets只使用唯一的元素)，这是问题的主要约束之一。这让我觉得我们需要某种哈希函数或hashmap来处理副本？我不确定.

我在互联网上找到的所有不同的算法都只处理打印元素，而不是索引，因此我对这个问题没有任何希望。

如果你们中的任何人知道这方面的最优算法，同时也满足约束条件并在O(n)时间内运行，我们将非常感谢您的帮助。提前谢谢你。

Answer 1

这里是一个伪代码回答你的问题，使用哈希表(或映射)和设置。我允许您使用经过调整的数据结构将其转换为cpp (在本例中，经典的hashmap和let将很好地完成这项工作)。

符号:我们将表示数组的A，n的长度，T的“和”。

// first we build a map element -> {set of indices corresponding to this element}
Let M be an empty map; // or hash map, or hash table, or dictionary
for i from 0 to n-1 do {
    Let e = A[i];
    if e is not a key of M then {
        M[e] = new_set()
    }
    M[e].add(i)
}

// Now we iterate over the elements
for each key e of M do {
    if T-e is a key of M then {
        display_combinations(M[e], M[T-e]);
    }
}

// The helper function display_combinations
function display_combinations(set1, set2) {
    for each element e1 of set1 do {
        for element e2 of set2 do {
            if e1 < e2 then {
                display "(e1, e2)";
            } else if e1 > e2 then {
                display "(e2, e1)";
            }
        }
    }
}

正如评论中所说的，在最坏的情况下，这种算法的复杂性在O(n²)中。如果数组的所有元素的值都是O(n²)，则输出的大小可能在T/2中，这是不能低于这种复杂性的一种方法。

编辑:这个伪代码不按顺序输出对。只需将它们存储在成对的数组中，并在显示该数组之前对其进行排序。同样，我没有处理一对(i, i)可能满足需求的情况。您可能需要考虑它(只需在最后一个循环中通过e1 > e2更改e1 >= e2 )