Есть ли более эффективный способ проверить, складываются ли два числа в списке в int, k?

Question

Я подписан на список рассылки проблем кодирования. Это было сегодня:

Учитывая список чисел и число k, верните, складывают ли любые два числа из списка k.

Например, учитывая [10, 15, 3, 7] и k из 17, верните true, так как 10 + 7 равно 17.

Бонус: Вы можете сделать это за один проход?

Я придумал следующее, но мне было интересно, если это самое эффективное решение.

bool found = false;
int k = 17;
list<int> given({10, 15, 3, 7});

int main() {
    for (int num : given) {
        found = find(given.begin(), given.end(), k - num) != given.end();

        if (found) break;
    }

    return found;
}

Код работает безупречно. Я просто хочу знать, может ли это быть более эффективным или я делаю что-нибудь в своем коде, который не одобряется на рабочем месте. Большое спасибо.

Answer 1

Вы можете перебирать массив один раз, используя набор.

int k = 17;
list<int> given({10, 15, 3, 7});
unordered_set<int> seen();

// O(n) time-complexity
int main() {
    // Iterate over O(n) items
    for (int num : given) {
        // O(1) operations
        if (seen.contains(k - num)) {
            // seen contains a value that is the difference between k and num. If you add num to that value, k - n + n = k, you have found two numbers that sum to k
            return true;
        } else {
            // Better luck next time, keep looking
            seen.add(num);
        }
    }

    return false;
}

Answer 2

Держите карту / словарь значений "необходимо".

• Сканирование по заданному,

• Требуется ли заданное значение?

  • , если да, то сделано

  • , в противном случае добавьте необходимое значение к необходимой карте

Возможно, это либо O (n), либо O (n log n) (в зависимости от производительности карты, и вы можете использовать набор)

псевдокод:

bool searchy( int wanted ) {
    bool found = false;
    needed = map<int,bool>{};
    for( each x in given ) {
        if( needed[x] ) then { return found = true; }
        else { needed[wanted - x] = false; }
    }

    return found;
}

И алгоритм на С ++

#include <map>
#include <list>
int wanted = 17;
std::list<int> given({10, 15, 3, 7});

bool searchy(int wanted) {
    bool found = false;
    std::map<int,bool> needed = {}; //could keep position of item matched...
    for (int x : given) {
        if( needed.count(x) > 0 ) { found = true; break; }
        else { needed[wanted - x] = false; }
    }
    if( found ) std::cout "found: (" << wanted - x << "+" << x << std::endl;
    return found;
}

int main() {
    bool found = searchy(wanted);
    return found;
}

Answer 3

Существует более быстрое решение со сложностью O (nlogn), не уверенное в O (n).

Подсказка: используйте метод с двумя указателями.

Сначала отсортируйте массив.

Есть два указателя - один начинается с индекса 0 и увеличивается, а другой начинается споследний индекс и убывающий.

Пусть значение, начинающееся с 0, будет a , а значение, начинающееся с последнего индекса b .

Если a + b больше целевого значения, то мы должны уменьшить индекс b . Помните, что числа перед индексом b меньше, чем число в индексе b .

Если a + bменьше целевого значения, мы должны увеличить индекс a , поскольку числа после индекса a образуют возрастающую последовательность.

sort(v.begin(), v.end());
    while(b>a){
        if (v[a]+v[b]==target) {
            //There exists such values
            return 0;
        }
        else if (v[a]+v[b]>target) {
            b--;
        }
        else {
            a++;
        }
    }