使用迭代器解决数组求和问题并仅测试相等性

Question

在准备采访时,我决定使用迭代器逻辑编写经典的"查找数组中有两个元素总结到给定数字"的问题,以便它可以推广到其他容器而不是vector.

到目前为止,这是我的功能

// Search given container for two elements with given sum. 
// If two such elements exist, return true and the iterators 
// pointing to the elements. 
bool hasElementSum( int sum, const vector<int>& v, vector<int>::iterator& el1, vector<int>::iterator& el2 )
{
    bool ret = false;
    el1 = v.begin();
    el2 = v.end()-1;
    while ( el1 != el2 ) {
        if ( *el1 + *el2 == sum ) return true;
        ++el1;--el2;
    }
    return false;
}

当然,这不起作用,但我不知道如何在不使用条件的情况下做到这一点while ( el1 >= el2 ).我看起来建议不要使用omnly对迭代器进行等式检查,以便能够推广到支持迭代器的所有类型的容器.

谢谢!

Answer 1

首先,你的算法是错误的,除非你以某种方式提前确定你只需要查看一个项目在集合的前半部分中的总和,另一个是在集合的后半部分.

如果输入没有排序,那么@ sbi的答案就差不多了.

使用排序的随机访问输入,您可以从第一个元素开始,并进行二分搜索(或插值搜索等)以查看是否可以找到与该值相关的值以生成所需的总和.然后你可以尝试第二个元素,但是当你进行二分搜索(或其他)时,使用前一个搜索的结果作为上限.由于您的第一个元素大于前一个元素,因此生成正确总和的匹配值必须小于或等于您上次查找的值.