Найти 2 элемента массива, сумма которых равна заданному числу

#массивы #алгоритм #числа

Задачка кажется очень простой, но все равно не выходит. 

Дан массив целых чисел, упорядоченный строго по возрастанию. 

Дано некоторое число X, нужно менее чем за квадратное количество операций(то есть
перебор всех пар) найти такие два любых элемента массива, что их сумма равна X, иначе
вывести 0.

Как сделать это меньше, чем за квадратное время?

Подкиньте идею какую-нибудь, ну или сам подход?))
Спасибо=) 
    

Ответы

Ответ 1

Решение за О(n):
Решаем методом "2 указателя"
Храним 2 индекса: первый сначала указывает на нулевой элемент, второй - на последний
элемент.
Цикл - пока индексы не будут равны (то есть пока они не укажут на один и тот же элемент.
Если такое случилось - значит, искомых элементов в массиве нет).
На каждой итерации цикла сравниваем текущую сумму (сумму элементов, на которые указывают
индексы) с искомой. Если сумма меньше - увеличиваем первый индекс, если сумма больше
- уменьшаем второй индекс. Если равна - решение найдено.

#include 
#include 

using namespace std;

int main()
{
    int *a; // массив
    int n; // количество элементов в массиве
    int sum; // необходимая сумма
    ///
    //чтение массива
    cin >> n;
    a = new int[n];
    for (int i = 0; i < n; i++)
        cin >> a[i];
    cin >> sum;
    ///
    // индексы
    int lt = 0; // первый, то есть левый
    int rt = n - 1; // второй, то есть правый
    while (lt != rt)
    {       
        int cursum = a[lt] + a[rt];
        if (cursum < sum)
            lt++;
        else if (cursum > sum)
            rt--;
        else // if (cursum == sum)
        {
            cout << "indexes: " << lt << " " << rt << endl;
            cout << "values: " << a[lt] << " " << a[rt] << endl;
            return 0;
        }
    }
    cout << "not found" << endl;
    return 0;
}


Ответ 2

Поскольку массив отсортирован, то этим фактом можно воспользоваться для поиска второго
элемента в паре с помощью бинарного поиска. Алгоритм следующий:


Проходим массив, для каждого элемента вычисляем, какая ему нужна
пара
Ищем эту пару с помощью бинарного поиска
Если элемент нашелся и это не текущий элемент, то мы нашли пару


Т.о. получим алгоритм со сложностью O(nlogn): цикл дает O(n), бинарный поиск дает
O(logn).

Примерный код:

bool found = false;

for (int i = 0; i < array.Length; i++)
{
    int first = array[i];
    int second = X - first; // искомый элемент
    int index = BinarySearch(array, second);
    if (index > -1 && index != i)
    {
        Console.WriteLine("{0} and {1}", i, index);
        found = true;
        break;
    }
}

if (!found)
{
    Console.WriteLine("No such pairs!");
}


Ответ 3

сосчитать необходимые дополнения до X для каждого элемента. Этой операциии не избежать.
Получится убывающий ряд.
двигаемся по обоим рядам от меньших к большим, пока не находится равенство. Тогда
пара найдена – значение и X минус значение.


Т.о. один раз пройти, вычисляя дополнения до X, и макс. 2 раза, разыскивая совпадения.
И по результатам, исключить дубли зеркальных пар, как (-3,15) в примере ниже.

Недостаток – нужно хранилище для 2 x размер данных. Это оптимизируется, но не будем
усложнять.

Пример:

X = 12, исходный ряд: -3 1 3 4 7 9 12 15

-3 1  3 4 7 9 12 15

дополнения до X:
15 11 9 8 5 3 0 -3

двигаем пошагово указатель на текущий элемент в каждом ряду
от меньших к большим,
если бОльшее значение в одном ряду, в другом ряду берём следующее,
если равны, то для след. шага сравнения берём по след. значению в обоих
-3 1 3 4 7 8 12 15
-3 0 3 5 8 9 11 15

Находим -3, значит, пара (-3, 12 - -3 = 15);
второе совпадение (3, 12-3=9);
третье совпадение (15, 12-15=-3);


Надо ещё пройтись по результатам и убрать зеркальные дубли пар, если есть (тут один
случай).



Upd не рассмотрел случай, если дополнение = значению и повтор одинаковых значений
в исходном массиве, напр. [1,3,3,4,4].


Ответ 4

Цикл К=1 до N-1
  Цикл H=K+1 до N
    Если A[K]+A[H] = X Вывод A[K], A[H] Стоп

Если нет пар, Вывод 0


A - Массив

N - Количество элементов

Тогда через бинарный поиск

Цикл К=1 до N-1
  M = X - A[K]
  Бинарный поиск М
    Если A[K]+М = X Вывод A[K], М Стоп

Если нет пар, Вывод 0


в бинарном поиске операций меньше, около log2(n)