Решение проблемы суммы массивов с использованием итераторов и проверка на равенство

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 ).Различные источники, которые я посмотрел, не советуют использовать проверку одинакового равенства для итераторов, чтобы иметь возможность обобщать все типы контейнеров, которые поддерживают итераторы.

Спасибо!

Answer 1

Прежде всего, ваш алгоритм неверен , если вы как-то не определили заранее, что вам нужно только смотреть на суммы, где один элемент находится в первой половине коллекции, а другой - во второй половине сборника.

Если входные данные не отсортированы, то ответ @ sbi примерно такой же хороший, как и получаемый.

С отсортированным вводом с произвольным доступом вы можете начать с первого элемента и выполнить бинарный поиск (или интерполяционный поиск и т. Д.), Чтобы выяснить, сможете ли вы найти значение, которое нужно будет использовать для получения желаемая сумма. Затем вы можете попробовать второй элемент, но когда вы выполняете бинарный поиск (или что-то еще), используйте результат предыдущего поиска в качестве верхнего предела. Поскольку ваш первый элемент больше предыдущего, соответствующее значение для получения правильной суммы должно быть меньше или равно значению, которое вы нашли в прошлый раз.

Answer 2

foreach element1 in array
  foreach element2 in array + &element1
    if( element1 + element2 == sum )
      return true
return false

Это O (N ^ 2), так как вы должны добавить каждый элемент к каждому из других элементов.

Answer 3

Разве этот вопрос обычно не задают с отсортированным массивом?
Если нет, то это должно работать в сложности O (n ^ 2), и вам нужно будет проверить все возможные пары.

Answer 4

Извините, я облажался. То, что я хотел написать, было сорта, за которым следовал линейный проход, который является типичным ответом на этот вопрос, как указывал Ицик в своем комментарии к Джерри, то есть что-то вроде

bool hasElementSum( int sum, const vector<int>& v, int* ind1, int* ind2 )
{

    *ind1 = 0; *ind2 = v.size()-1;

    std::sort( v.begin(), v.end() );

    while ( *ind1 <= *ind2 ) {
        int s = v[*ind1] + v[*ind2];
        if ( s > sum ) (*ind1)++;
        else if ( s < sum ) (*ind2)++;
        else return true
    }
    return false;
}

Мой вопрос состоял в том, как написать это, используя итераторы, не говоря while (iter1 <= iter2 ), чтобы быть общим, но теперь я вижу, что это не имеет смысла, потому что этот алгоритм все равно нуждается в итераторах с произвольным доступом. Кроме того, возвращать индексы не имеет смысла, поскольку они ссылаются на отсортированный массив, а не на исходный.

Answer 5

Я предлагаю следующий метод, хотя не анализировал порядок

Построить двоичное дерево поиска со всеми элементами вектора, затем для каждого элемента

foreach(element = vec.begin to vec.end)
{
    if element == node.data, skip

    if the element + node.data == sum, return true

    if the element + node.data > sum, goto left child

    if the element + node.data < sum, goto right child
}

Не идеальное решение / алгоритм, но что-то в этом роде.