Summe in einem Array finden

Question

Ich habe dieses Programm, das 2 Zahlen im Array findet (unsortiert), so dass seine Summe der Zielsumme entspricht. Hier ist mein Programm:

vector<int> findNumbers(vector<int>& nums, int target) 
    {
        vector<int> result;
        for(int i = 0; i < nums.size() - 1; i++)
            for(int j = i + 1; j < nums.size(); j++)
                if(nums[i] + nums[j] == target)
                {
                    result.push_back(i);
                    result.push_back(j);
                    return result;
                }
        return result;
    }

Aber in der letzten Zeile scheint das Rückgabeergebnis nichts zu bewirken, denn wenn die Zahlen gefunden werden, wird es bereits vorher zurückgegeben, aber wenn ich es entferne, wird es einen Fehler verursachen. Verlangsamt die letzte Zeile mein Programm?

Answer 1

Frage

Verlangsamt die letzte Zeile mein Programm?

Dies hängt davon ab, was Sie zurückgeben möchten, wenn es keine Paare gibt, die sich summieren target. Wenn Sie die letzte Zeile weglassen, ruft Ihr Programm ein undefiniertes Verhalten auf, wenn der Kontrollfluss das Ende des Funktionskörpers erreicht, und der Compiler warnt Sie zu Recht davor.

Ganzzahliger Überlauf

Es gibt einen Randfall, den Ihr Code nicht verarbeiten kann - einen Ganzzahlüberlauf. Wenn die Summe von nums[i]und nums[j]den Bereich von überschreitet int, wird undefiniertes Verhalten aufgerufen.

Sofortige Verbesserungen

Hier sind einige Verbesserungen an Ihrem Code:

• numssollte als constReferenz genommen werden , da es innerhalb der Funktion nicht geändert wird.

• A vectorsollte mit a std::size_t(oder seinem size_typeElementtyp) indiziert werden , da dies nums.size()den Bereich von überschreiten kann int.

• Wenn numsleer ist, nums.size() - 1wird produziert SIZE_MAX, was in der Regel \ ist$2^{32} - 1\$oder \$2^{64} - 1\$. Dies hat in diesem speziellen Fall keinen Fehler verursacht, aber es ist definitiv ein logischer Fehler, der beispielsweise durch ein Spezialgehäuse behoben werden sollte nums.size() < 2.

• Sie müssen resultam Anfang kein Leerzeichen erstellen - erstellen Sie es beispielsweise im laufenden Betrieb return {nums[i], nums[j]}.

Hier ist das Ergebnis: (Überlaufprüfung wird der Einfachheit halber weggelassen)

#include <cstddef>
#include <vector>

std::vector<std::size_t>
find_numbers(const std::vector<int>& nums, int target) {
    if (nums.size() < 2) {
        return {};
    }

    for (std::size_t i = 0; i < nums.size() - 1; ++i) {
        for (std::size_t j = i + 1; j < nums.size(); ++j) {
            if (nums[i] + nums[j] == target) {
                return {i, j};
            }
        }
    }

    return {};
}

Verallgemeinerung

Die Funktion kann flexibler gestaltet werden, indem ein Iteratorpaar und ein Funktor verwendet werden:

#include <iterator>
#include <utility>

// returns a pair of iterators [it_a, it_b]
// such that it_a <= it_b && pred(*it_a, *it_b)
// or [last, last] if such a pair is not found
template <typename ForwardIterator, typename BinaryPredicate>
auto find_pair(
    ForwardIterator first,
    ForwardIterator last,
    BinaryPredicate pred
) -> std::pair<ForwardIterator, ForwardIterator> {
    if (first == last) {
        return {last, last};
    }

    for (auto next = std::next(first); next != last; ++first, ++next) {
        for (auto it = next; it != last; ++it) {
            if (pred(*first, *it)) {
                return {first, it};
            }
        }
    }

    return {last, last};
}

Optimierung

Der ursprüngliche Algorithmus läuft in \$O(n^2)\$Zeit, die auf \ verbessert werden kann$O(n \log n)\$ für große Eingänge:

• Pflegen Sie zunächst einen Indexvektor, der nach den Zahlen sortiert ist.

• Für jede Zahl binäre Suche nach target - number.

Answer 2

Tolle Antwort von LF. In Bezug auf die Optimierung kann dies sogar in O (n) entweder mit einem Hash erfolgen (vorausgesetzt, es gibt nicht zu viele Hash-Kollisionen):

std::vector<size_t>
findNumbers(
        std::vector<int> const & nums,
        int const                target )
{
    // pack numbers and indices into hash
    std::unordered_map<int,size_t> hash;
    hash.reserve( nums.size() );
    for( size_t i=0; i<nums.size(); ++i ) {
        hash.emplace( nums[i], i );
    }

    // for every number search for "target - number"
    for( size_t i=0; i<nums.size(); ++i )
    {
        auto const el = hash.find( target - nums[i] );
        if (   (el != hash.end())
            && (i  != el->second) )
        {
            return { i, el->second };
        }
    }
    
    return {};
}

Oder indem Sie eine der nicht vergleichbaren Sorten verwenden.