C++ – Mapiranje i nizovi

Cilj: Eliminasti O(n x n) kompleksnost.

Zadatak: Pronaci dva broja u nizu koji imaju zbir X.

#include <iostream>
#include <unordered_map>

using namespace std;

bool nadjiSabirke(int brojevi[], int duzina, int cilj, int &indeks1, int &indeks2) {
    unordered_map<int, int> vidjeni; // vrijednost -> indeks

    for (int i = 0; i < duzina; i++) {
        int potrebno = cilj - brojevi[i];

        // Ako smo vec vidjeli broj koji nam treba
        if (vidjeni.count(potrebno)) {
            indeks1 = vidjeni[potrebno];
            indeks2 = i;
            return true;
        }

        // Zapamti trenutni broj i njegov indeks
        vidjeni[brojevi[i]] = i;
    }

    return false;
}

int main() {
    int brojevi[6] = {3, 2, 6, 7, 11, 8};
    int duzina = 6;
    int cilj = 15;
    int i1, i2;

    if (nadjiSabirke(brojevi, duzina, cilj, i1, i2)) {
        cout << "Indeksi koji daju zbir " << cilj << ": " << i1 << " i " << i2 << endl;
        cout << "Vrijednosti: " << brojevi[i1] << " + " << brojevi[i2] << " = " << cilj << endl;
    } else {
        cout << "Nema rjesenja" << endl;
    }

    return 0;
}