11246. Sum of three

Given an array of integers A and an integer x. Find a triplet of numbers (A_i, A_j, A_k) in the array whose sum equals x. All indices i, j, k should be different.

Input. The first line contains the size of the array n (n ≤ 3 * 10⁴) and the value of x (|x| ≤ 10⁹). The second line contains n integers, each of which does not exceed 10⁸ in absolute value.

Output. If the required triplet exists, print it in any order. If multiple triplets exist, print any one of them. If the desired triplet does not exist, print -1.

Sample input	Sample output
8 19 20 3 5 1 15 7 17 12	1 3 15

SOLUTION

two pointers

Algorithm analysis

Let a₀, a₁, …, a_n-1 be an input array. Iterate through all possible indices k = 0, 1, …, n – 3. Then, for each value of k, find a pair of indices (i, j) such that i > k and a_i + a_j = x – a_k (i < j). This can be achieved on a sorted array using the two-pointer technique in linear time.

Algorithm realization

Read the input data.

cin >> n >> x;

v.resize(n);

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

cin >> v[i];

Sort the input array.

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

Iterate through the values k = 0, 1, …, n – 3.

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

{

Find a pair of indices (i, j) such that i > k and v_i + v_j = x – v_k (i < j). Initialize the indices i and j.

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

s = x - v[k];

Use the two-pointer technique to find the desired pair (i, j).

while (i < j)

{

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

{

If the pair (i, j) is found, print the desired triplet of numbers (v_k, v_i, v_j).

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

return 0;

}

If v[i] + v[j] < s, then move pointer i one position to the right;

If v[i] + v[j] > s, then move pointer j one position to the left;

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

}

}

If the triplet of numbers is not found, print -1.

cout << -1 << endl;

Python realization

Read the input data.

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

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

Sort the input list.

v.sort()

Iterate through the values k = 0, 1, …, n – 3.

for k in range(n - 2):

Find a pair of indices (i, j) such that i > k and v_i + v_j = x – v_k (i < j). Initialize the indices i and j.

i, j = k + 1, n – 1

s = x - v[k]

Use the two-pointer technique to find the desired pair (i, j).

while i < j:

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

If the pair (i, j) is found, print the desired triplet of numbers (v_k, v_i, v_j).

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

exit(0)

If v[i] + v[j] < s, then move pointer i one position to the right;

If v[i] + v[j] > s, then move pointer j one position to the left;

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

i += 1

else:

j -= 1

If the triplet of numbers is not found, print -1.

print(-1)