Descubra em tempo linear se existe um par no vetor classificado que agrega certo valor

Dado um std::vectordos elementos distintos classificados em ordem crescente, quero desenvolver um algoritmo que determine se há dois elementos na coleção cuja soma é um determinado valor sum,.

Eu tentei duas abordagens diferentes com suas respectivas vantagens e desvantagens:

1. Posso digitalizar o vetor inteiro e, para cada elemento do vetor, aplicar search binário ( std::lower_bound) no vetor para pesquisar um elemento correspondente à diferença entre sume o elemento atual. Esta é uma solução de tempo O (n log n) que não requer espaço adicional.

2. Eu posso atravessar o vetor inteiro e preencher um std::unordered_set. Então, digitalizo o vetor e, para cada elemento, procuro std::unordered_seta diferença entre sume o elemento atual. Como a pesquisa em uma tabela de hash é executada em tempo constante, em média, essa solução é executada em tempo linear. No entanto, essa solução requer espaço linear adicional devido à std::unordered_setestrutura de dados.

No entanto, estou procurando uma solução que seja executada em tempo linear e não exija espaço linear adicional. Alguma ideia? Parece que sou forçado a trocar velocidade por espaço.

Como o std::vectorjá está classificado e você pode calcular a soma de um par em tempo real , é possível obter uma solução de tempo linear no tamanho do vetor com espaço O (1).

A seguir, uma implementação do tipo STL que não requer espaço adicional e é executada em tempo linear:

template<typename BidirIt, typename T>
bool has_pair_sum(BidirIt first, BidirIt last, T sum) {
    if (first == last)
        return false; // empty range

   for (--last; first != last;) {
      if ((*first + *last) == sum)
         return true; // pair found

      if ((*first + *last) > sum)
         --last; // decrease pair sum
      else // (*first + *last) < sum (trichotomy)
         ++first; // increase pair sum
   }

    return false;
}

A idéia é atravessar o vetor de ambas as extremidades - frente e verso - em direções opostas ao mesmo tempo e calcular a soma do par de elementos enquanto o faz.

No início, o par consiste nos elementos com os valores mais baixo e mais alto, respectivamente. Se a soma resultante for menor que sum, avance first- o iterador apontando para a extremidade esquerda. Caso contrário, mova last- o iterador apontando para a extremidade direita - para trás. Dessa forma, a soma resultante se aproxima progressivamente de sum. Se os dois iteradores acabarem apontando para o mesmo elemento e nenhum par cuja soma for igual a sumfor encontrado, não haverá esse par.

auto main() -> int {
   std::vector<int> vec{1, 3, 4, 7, 11, 13, 17};

   std::cout << has_pair_sum(vec.begin(), vec.end(), 2) << ' ';
   std::cout << has_pair_sum(vec.begin(), vec.end(), 7) << ' ';
   std::cout << has_pair_sum(vec.begin(), vec.end(), 19) << ' ';
   std::cout << has_pair_sum(vec.begin(), vec.end(), 30) << '\n';
}

A saída é:

0 1 0 1

Graças à natureza genérica do modelo de função has_pair_sum()e como requer apenas iteradores bidirecionais, esta solução também funciona com std::list:

std::list<int> lst{1, 3, 4, 7, 11, 13, 17};
has_pair_sum(lst.begin(), lst.end(), 2);

Eu tive a mesma ideia que a da resposta de 眠 り ネ ロ ク , mas com uma implementação um pouco mais compreensível.

bool has_pair_sum(std::vector<int> v, int sum){
    if(v.empty())
        return false;

    std::vector<int>::iterator p1 = v.begin();
    std::vector<int>::iterator p2 = v.end(); // points to the End(Null-terminator), after the last element
    p2--; // Now it points to the last element.

    while(p1 != p2){  
        if(*p1 + *p2 == sum)
            return true;
        else if(*p1 + *p2 < sum){ 
            p1++;
        }else{
            p2--;
        }
    }

    return false;
}

bem, como já recebemos uma matriz classificada, podemos fazê-lo com duas abordagens de ponteiro, primeiro mantemos um ponteiro esquerdo no início da matriz e um ponteiro direito no final da matriz e, em cada iteração, verificamos se a soma do valor de o índice do ponteiro esquerdo e o valor do índice do ponteiro direito são iguais ou não; se sim, retornam daqui; caso contrário, temos que decidir como reduzir o limite, ou seja, aumentar o ponteiro esquerdo ou diminuir o ponteiro direito; por isso, comparamos a soma temporária com dada soma e se essa soma temporária for maior que a soma especificada, decidimos reduzir o ponteiro direito; se aumentarmos o ponteiro esquerdo, a soma temporária permanecerá igual ou apenas aumentará, mas nunca menor, portanto, decidimos reduzir o ponteiro direito para que a soma temporária diminui e chegamos perto de nossa soma determinada, semelhante se a soma temporária for menor que a soma dada,portanto, nenhum significado de reduzir o ponteiro direito como soma temporária permanecerá soma ou diminuirá mais, mas nunca aumentará, portanto aumentamos nosso ponteiro esquerdo para que nossa soma temporária aumente e alcancemos a quantia próxima, e fazemos o mesmo processo repetidamente, a menos que obter a soma igual ou o valor do índice do ponteiro esquerdo se tornar maior que o índice do ponteiro direito ou vice-versa abaixo é o código para demonstração, deixe-me saber se algo não estiver clarodeixe-me saber se algo não está clarodeixe-me saber se algo não está claro

bool pairSumExists(vector<int> &a, int &sum){
    if(a.empty())
    return false;

    int len = a.size();
    int left_pointer = 0  , right_pointer = len - 1;

    while(left_pointer < right_pointer){
        if(a[left_pointer] + a[right_pointer] == sum){
            return true;
        }
        if(a[left_pointer] + a[right_pointer] > sum){
            --right_pointer;
        }
        else
        if(a[left_pointer] + a[right_poitner] < sum){
            ++left_pointer;
        }
    }
    return false;
}