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

Задачка кажется очень простой, но все равно не выходит.
Дан массив целых чисел, упорядоченный строго по возрастанию.
Дано некоторое число X, нужно менее чем за квадратное количество операций(то есть перебор всех пар) найти такие два любых элемента массива, что их сумма равна X, иначе вывести 0.
Как сделать это меньше, чем за квадратное время?
Подкиньте идею какую-нибудь, ну или сам подход?)) Спасибо=)

Ответ

Решение за О(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; }