Desafío de Programación para Refugio 33

[GabrielEValenzuela]

En Refugio 33, cada semana recibimos una cierta cantidad de donaciones (en unidades, por ejemplo: alimentos, mantas, botellas de agua). Cada donación está representada como un número entero en una lista.

Dado un número objetivo que representa la cantidad específica de suministros que necesitamos cubrir una necesidad concreta (por ejemplo, para una familia o actividad comunitaria específica), tu misión es ayudarnos a encontrar dos donaciones que, sumadas, alcancen exactamente ese número objetivo.

📥 Entrada

• Una lista de números enteros donaciones que representa la cantidad de unidades de cada ítem recibido.
• Un número entero objetivo que representa la cantidad exacta de recursos que necesitamos.

std::vector<int>& indicesDonaciones(const std::vector<int>& donations, int target);

🎯 Salida

• Devuelve los índices (posiciones) de las dos donaciones que suman exactamente objetivo.

Puedes asumir que siempre habrá una única solución posible. No se puede usar la misma donación dos veces.

🧪 Ejemplo

donaciones = [3, 7, 11, 15]
objetivo = 18

Salida esperada:

[1, 2]  # porque donaciones[1] + donaciones[2] == 7 + 11 == 18

✅ Reglas

• Cada donación solo puede usarse una vez.
• Puedes devolver los índices en cualquier orden (por ejemplo, [1, 2] o [2, 1] son válidos).

[benjabrezzo]

#include <vector>
#include <unordered_map>

std::vector<int>& indicesDonaciones(const std::vector<int>& donations, int target) {
    std::unordered_map<int, int> indices; // Clave -> Valor es Donacion -> Indice

    for(int i = 0; i < donations.size(); ++i) {
        // valorNecesario es el target menos el valor de la donacion i, y se busca el complemento que de el target en el resto del vector donations
        int valorNecesario = target - donations[i]; 
        
        if(indices.find(valorNecesario) != indices.end()) {
            return {indices[valorNecesario], i); // se devuelve el indice del valor necesario y el indice del valor actual
        }
        
        // Inicialmente el unordered map va a estar vacio, y para i = 0 no se va a encontrar el complemento, pero 
        // a partir de este se empiezan a agregar al unordered map las donaciones con su respectivo indice y para 
        //las proximas iteraciones, si ya se agrego el complemento, el codicional se cumplira
        indices[donations[i]] = i;  
    }

    return {}; // Solo se devuelve la lista vacia si no se encontraron dos donaciones que sumen el target, si se encuentran no deberia llegar a esta parte del codigo
}

[Danteps-4]

std::vector<int> indicesDonaciones(const std::vector<int>& donations, int target) {
  std::unordered_map<int, int> indices;  // valor -> indice

  for (int i = 0; i < donations.size(); i++) {
    int complemento = target-donations[i];
    if (indices.count(complemento) > 0) {
      return {indices[complemento], i};
    }

    indices[donations[i]] = i;
  }
  return {};
}