Wydajne wykonanie algorytmu

Hej,
dana jest tablica liczb np.
std::vector<int> vec = {1, 4, 3, 6, 2, 7, 1};

uzupełnij funkcję:
std::vector<std::pair<int>> func(const std::vector<int>& vec, const int requestedNumber);

tak aby z podanego vec wybrać takie dwie liczby, których suma wynosi requestedNumber.
Wynik dla podanego vec i requestedNumber(4) powinien wyglądać następująco:
{ {1, 3}, {3, 1} }, czyli jest to liczba o indeksie [0, 2] oraz [2, 6].

Ktoś ma jakiś pomysł jak to zrobić, tak aby złożoność wynosiła mniej jak O(n^2)?

Doprecyzuj czy:

1. chcesz wydajnie wykonać algorytm,
2. chcesz wykonać wydajny algorytm,

bo to jednak zupełnie różne podejścia do problemu.

@Focusx:
Najprościej będzie zrobić hashamape i dla każdego elementu sprawdzać, czy wcześniej wystąpiła poszukiwana liczba.

Są dwa sensowne rozwiązania: haszowanie, jak @leto wyżej pisze (tworzysz sobie pusty zbiór, po czym lecisz po wektorze i patrzysz, czy dla napotkanego i z wektora jest w zbiorze suma - i; jeśli jest, to super, właśnie znalazłeś parę, jeśli nie, to wrzucasz do zbioru i idziesz dalej); oraz sortowanie (sortujesz wektor i idziesz zaczynając od przeciwnych końców, patrzysz czy się sumują do suma; jak tak, to znalazłeś parę, jak się sumują do czegoś większego, to obniżasz wynik cofając prawy koniec, a jak coś mniejszego, to zwiększasz wynik przesuwając lewy; jak się Ci wskaźniki zrównają, to znaczy że nie ma).

Nie jestem pewien, które rozwiązanie będzie szybsze. Haszowanie ma niby niższą złożoność obliczeniową, ale za to znacznie większe stałe — wypada zatem puścić trochę benchmarków, żeby się przekonać.

Althorion napisał(a):

Nie jestem pewien, które rozwiązanie będzie szybsze. Haszowanie ma niby niższą złożoność obliczeniową, ale za to znacznie większe stałe — wypada zatem puścić trochę benchmarków, żeby się przekonać.

Ta książka tutaj
https://cses.fi/book/book.pdf
w punkcie Basic Techniques -> Data Structures -> Comparison to sorting mówi, że sortowanie powinno być szybsze koło dwóch razy na różnych przekrojach danych (btw. jest tam opisany podobny problem).

Podejście teoretyczne i idealistyczne
Wrzucasz wszystkie liczby do hash mapy. n liczb, wrzucenie do hash mapy 1 elementu O(1). Całość O(n)

Dla każdej liczby a wyliczenie b = sum - a i sprawdzenie, czy b jest w hash map. n liczb do sprawdzenie, idealnie sprawdzenie czy b jest w hashmapie O(1). Całość O(n)

Ponieważ O(n) + O(n) = O(n) to całość zadania ma O(n)

W praktyce, jakby to na konkretnym zestawie danych benchmarkować, to hash map załadowana np. w 50% nie ma pobrania O(1) bo w jednym bucket będzie więcej jak jedno trafienie po wyliczeniu hash dla klucza i modulo dla rozmiaru bucketów.
Konflikt może być rozwiązany linked list, można iść w red black tree, albo mądrzy ludzie 'theoretical computer science' u Smoka wiedzą jak (ja jestem za cienki)

Po treści wnioskuję, że w zadaniu chodzi o pokazanie, że O(n) i na tym koniec.

*W praktyce zależy od implementacji.
Np. weżmy nie C/C++ ale JavaScript. Dwie klamry {} to już hashmap. Konia z rzędem i wóz szacunku dla tego kto będzie wgłębiony w implementację tego w ES5, ES6, ES2018.
W Java też, większość materiałów uczy o LinkedList w HashMap a jak pamiętam, od którejś wersji implementacja została zmieniona na self-balancing tree

Pytanie czy wynik to musi być { {1, 3}, {3, 1} }
czy może też być { {1, 3}, {1, 3} }.
Czy kolejność liczb w parach i kolejność samych par ma znaczenie?

tak aby z podanego vec wybrać takie dwie liczby, których suma wynosi requestedNumber.

Tutaj potrzeba doprecyzować.Na przykład dla zbioru {1,1,1,1,1,1} i requestedNumber równego 2, ile par {1,1} będzie spełniało warunki zadania. Czy będzie to liczba kombinacji **dwu **elementowych z 6? W takim przypadku algorytm dla n-elementowego wektora wejściowego - w najgorszym przypadku - będzie zwracał rozwiązanie składające się z (n-1)n/2 elementów?

Przed wrzuceniem do hashmapy/drzewa ja bym jeszcze dodał warunek żeby nie wrzucać liczb większych niż requestedNumber wówczas hashmapa będzie mniejsza.

Czitels napisał(a):

Przed wrzuceniem do hashmapy/drzewa ja bym jeszcze dodał warunek

Jak damy warunki na zakres liczb to sortowanie bucket sort O(n)
Wtedy bierzemy dwie skrajne liczny z tablicy : mamy 2 wskaania na left = array[0] i right = array[lenght-1]
a) ich suma jest tą której szukamy => mamy parę
b) ich suma jest mniejsza od tej której szukamy => left = left+1 // suma jest już za mała, więc trzeba szukać szczęścia z lewej strony biorąc następną, większą liczbę (albo równą jak są równe) (gdyby brać z prawej mniejszą, to do obecnie już za małej sumy wzięlibyśmy jeszcze mniejszy składnik -> suma będzie jeszcze mniejsza, co jest złym kierunkiem)
c) ich suma jest większa od tej której szukamy => right = rigt - 1 // suma jest już za duża, więc trzeba szukać szczęścia z prawej strony biorąc następną, mniejszą liczbę (albo równą jak liczby w tablicy są równe / powtarzają się)

lecimy w pętli dopóki left < right

Mamy posortowaną tablicę, to trochę podobnie leci znany chyba każdemu z zaliczeń ASD BinarySearch

Jak nie znamy zakresu to konieczne sortowanie O(nlogn) daje ostatecznie dla całego zadania O(nlogn) + O(n) = O(nlogn), więc z hash map O(n) jest lepszym podejściem.

Gdy można posortować O(n) to teoretycznie oba rozwiązania są dobre na O(n)

PS
W C nie wiem (nie ma w standard library), ale w C++ hash map jest, więc do wyboru np. na interview (czas + stres) implementacja własna bucket sort czy użycie gotowej hash map? to zdecydowanie preferowałbym rozwiązanie z hash map.

Po co sortować?
Zrobić histogram (std::unordered_map<int, size_t>), z niego znaleźć wymaganą parę wartości, odnaleźć wartości, koniec.
Złożoność wychodzi liniowa.

template<typename T>
struct ValuePos
{
    T val;
    size_t pos;
};

template<typename T, typename It>
std::optional<std::pair<ValuePos<T>, ValuePos<T>>> find_pair_with_sum(It b, It e, T sum)
{
    std::unordered_map<T, size_t> values;
    size_t i = 0;
    while (b != e)
    {
        auto y = sum - *b;
        auto other = values.find(y);
        if (other != values.end())
        {
            return std::make_pair(ValuePos<T>{ other->first, other->second }, 
                                  ValuePos<T>{*b, i});
        }
        values.emplace(*b++, i++);
    }
    return {};
}

https://godbolt.org/z/dKTadr