Sum of three (Editorial)

Let a_0, a_1, ..., 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)