11246. Сумма трех

Задан массив целых чисел A и целое число x. Найдите такую тройку чисел (A_i, A_j, A_k) в массиве, сумма которых равна x. Все индексы i, j, k должны быть различны.

Вход. Первая строка содержит размер массива n (n ≤ 3 * 10⁴) и значение x (|x| ≤ 10⁹). Вторая строка содержит n целых чисел, каждое из которых по модулю не больше 10⁸.

Выход. Если требуемая тройка чисел существует, то выведите ее в любом порядке. Если существует несколько троек, выведите любую. Если искомой тройки не существует, выведите -1.

Пример входа	Пример выхода
8 19 20 3 5 1 15 7 17 12	1 3 15

РЕШЕНИЕ

два указателя

Анализ алгоритма

Пусть a₀, a₁, …, a_n-1 – входной массив. Переберем все возможные индексы k = 0, 1, …, n – 3. Далее для каждого значения k найдем такую пару индексов (i, j) что i > k и a_i + a_j = x – a_k (i < j). Это можно сделать на отсортированном массиве с помощью техники двух указателей за линейное время.

Реализация алгоритма

Читаем входные данные.

cin >> n >> x;

v.resize(n);

for (i = 0; i < n; i++)

cin >> v[i];

Сортируем входной массив.

sort(v.begin(), v.end());

Перебираем значения k = 0, 1, …, n – 3.

for (k = 0; k < n - 2; k++)

{

Ищем такую пару индексов (i, j), что i > k и v_i + v_j = x – v_k (i < j). Инициализируем индексы i и j.

i = k + 1; j = n - 1;

s = x - v[k];

Используем технику двух указателей для поиска искомой пары (i, j).

while (i < j)

{

if (v[i] + v[j] == s)

{

Если пара (i, j) найдена, то выводим искомую тройку чисел (v_k, v_i, v_j).

printf("%d %d %d\n", v[k], v[i], v[j]);

return 0;

}

Если v[i] + v[j] < s, то двигаем указатель i на одну позицию вправо;

Если v[i] + v[j] > s, то двигаем указатель j на одну позицию влево;

if (v[i] + v[j] < s) i++; else j--;

}

}

Если тройка чисел не найдена, то выводим -1.

cout << -1 << endl;

Python реализация

Читаем входные данные.

n, x = map(int, input().split())

v = list(map(int, input().split()))

Сортируем входной список.

v.sort()

Перебираем значения k = 0, 1, …, n – 3.

for k in range(n - 2):

Ищем такую пару индексов (i, j), что i > k и v_i + v_j = x – v_k (i < j). Инициализируем индексы i и j.

i, j = k + 1, n – 1

s = x - v[k]

Используем технику двух указателей для поиска искомой пары (i, j).

while i < j:

if v[i] + v[j] == s:

Если пара (i, j) найдена, то выводим искомую тройку чисел (v_k, v_i, v_j).

print(v[k], v[i], v[j])

exit(0)

Если v[i] + v[j] < s, то двигаем указатель i на одну позицию вправо;

Если v[i] + v[j] > s, то двигаем указатель j на одну позицию влево;

elif v[i] + v[j] < s:

i += 1

else:

j -= 1

Если тройка чисел не найдена, то выводим -1.

print(-1)