Skip to Content

Sum of Three Values

Solución

Explicación

Este problema es una extensión del problema de la suma de dos valores (two sum), ahora con tres valores. Podemos fijar el tercer puntero en cierto valor del arreglo y entonces el problema se convierte en el de la suma de dos valores discutido antes en este módulo.

Primero ordenaremos el arreglo. Luego recorremos todos los valores posibles para el tercer puntero y comprobamos si los tres punteros suman la cantidad objetivo, xx, teniendo posiciones distintas. Podemos mantener las posiciones originales de todos los valores guardando los pares {a[i],i}.

Implementación

Complejidad temporal: O(N2)\mathcal{O}(N^2)

#include <bits/stdc++.h> using namespace std; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n, x; cin >> n >> x; vector<pair<int, int>> arr; for (int i = 1; i <= n; i++) { int a; cin >> a; pair<int, int> p; p.first = a; p.second = i; // el primero del par representa el valor, el segundo el índice arr.push_back(p); } sort(begin(arr), end(arr)); for (int i = 0; i < n; i++) { int l, r; l = 0; r = n - 1; while (l != r) { int target; target = x - arr.at(i).first; if (l != i && r != i && arr.at(l).first + arr.at(r).first == target) { cout << arr.at(i).second << " " << arr.at(l).second << " " << arr.at(r).second << endl; return 0; } if (arr.at(l).first + arr.at(r).first < target) { l++; } else { r--; } } } cout << "IMPOSSIBLE" << endl; }
import java.io.*; import java.util.*; public class SumOfThreeValues { static class Group implements Comparable<Group> { int value, index; Group(int value, int index) { this.value = value; this.index = index; } @Override public int compareTo(Group other) { return Integer.compare(this.value, other.value); } } public static void main(String[] args) { Kattio io = new Kattio(); int n = io.nextInt(); int x = io.nextInt(); Group[] data = new Group[n]; for (int i = 1; i <= n; i++) { // guardamos la entrada en una clase que tiene un valor y un índice int value = io.nextInt(); Group group = new Group(value, i); data[i - 1] = group; } Arrays.sort(data); // dejamos los valores en orden creciente for (int i = 0; i < n; i++) { int left = 0; int right = n - 1; while (left != right) { int target = x - data[i].value; // si los tres valores suman el objetivo y no provienen del // mismo índice, encontramos nuestra respuesta if (left != i && right != i && data[left].value + data[right].value == target) { // tenemos una respuesta, la imprimimos io.println(data[i].index + " " + data[left].index + " " + data[right].index); io.close(); System.exit(0); // ya podemos terminar el programa } // no es igual al objetivo: aumentamos left si la suma es menor if (data[left].value + data[right].value < target) { left++; } // no es igual al objetivo: disminuimos right si la suma // es mayor que el objetivo else { right--; } } } // imprimimos IMPOSSIBLE si llegamos al final sin respuesta io.println("IMPOSSIBLE"); io.close(); } // CodeSnip{Kattio} }
n, x = map(int, input().split()) a = list(map(int, input().split())) p = [(a[i], i + 1) for i in range(n)] p.sort() for i in range(n): left = 0 right = n - 1 while left < right: target = x - p[i][0] """ si los valores suman el objetivo y no provienen del mismo índice, encontramos la respuesta """ if left != i and right != i and p[left][0] + p[right][0] == target: print(p[left][1], p[right][1], p[i][1]) exit() # aumentamos left si la suma es menor elif p[left][0] + p[right][0] < target: left += 1 # en caso contrario disminuimos right else: right -= 1 print("IMPOSSIBLE")