Метод двух указателей

Малоэффективное решение

Первое, что приходит в голову, — пройтись по всем парам элементов массива A[i] и A[j] и сравнить их сумму с X. Это можно сделать с помощью вложенного цикла:

Сложность такого алгоритма — O(n²).

Эффективное решение

Теперь применим методов двух указателей. В качестве двух указателей будут выступать две переменные, которые в начале хранят индексы первого и последнего элемента. На каждой итерации будем сравнивать сумму элементов, на которые указывают указатели. Если сумма элементов больше X, то нужно подвинуть правый указатель влево, чтобы сумма элементов уменьшилась (массив отсортирован). Если же сумма элементов меньше нужной, то подвинем левый указатель вправо. И так до тех пор, пока не найдем нужные элементы или же не попадем в ситуацию, когда два указателя определяют один и тот же элемент.

Так как по каждому элементу мы проходимся максимум один раз, то итоговая сложность — O(n).

На простом примере покажем, что выполняет код в процессе работы:

Как это работает?

В данной задаче алгоритм использует тот факт, что массив отсортирован. На каждой итерации, если сумма больше нужной, нам нужно двигать лишь правый указатель влево, так как во всех других случаях сумма только увеличится. Точно такая же логика применяется для случая, когда сумма меньше нужной.