Помогите ускорить/улучшить код на c++

Question

#include <iostream>
using namespace std;

int main(){

    int n, x;
    cin >> n >> x;
    int array[n];

    for (int i = 0; i < n; i++){
        cin >> array[i];
    }

    for (int i = 0; i < n; i++){
        for (int j = 1; j <= n; j++) {
            if ((array[i] + array[j]) == x) {
                cout << "YES";
                return 0;
            }
        }
    }
    cout << "NO";

    return 0;

}

Answer 1

Понимаете, "ускорить код" обычно подразумевает мелкие улучшения, в то время как ваш код работает за время O(N²) а задача решаема за O(N). Код надо переписывать полностью.

Быстрее всего будет работать вариант с двумя индексами — вы идете слева, от минимального значения, и двигаетесь справа, пока сумма этого левого элемента с правым не станет равной (ура! нашли! пишем Yes и выходим) или меньшей требуемого значения. Стала меньше? Точно так же двигаем левую границу, пока... Потом опять правую, пока...

Если границы встретились - все, выводим NO.

Думаю, вы теперь и сами справитесь?

А в качестве утешения - решение O(N log N), с бинарным поиском, которое тоже проходит по времени. Но тем не менее, это не O(N), так что дерзайте! :) Улучшать еще есть куда...

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main(int argc, char * argv[])
{
    int n, x;
    cin >> n >> x;
    vector<int> a(n);
    for(int i = 0; i < n; ++i) cin >> a[i];
    for(int i = 0; i < n-1; ++i)
    {
        if (binary_search(a.begin()+i+1,a.end(),x-a[i]))
        {
            cout << "YES";
            return 0;
        }
    }
    cout << "NO";

}

БЛОГ НА HUSL

Помогите ускорить/улучшить код на c++

Ответы (1 шт):