Skip to content

Instantly share code, notes, and snippets.

@juliafealves
Last active October 20, 2018 22:58
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save juliafealves/e1b1b0175ef31e0cad19de04df19844b to your computer and use it in GitHub Desktop.
➕ Dado um array de inteiros nao ordenado, encontrar o par cuja soma é um dado valor.
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
/**
* Dado um array de inteiros nao ordenado, encontrar o par cuja soma é um dado valor (se for possível encontrar dois
* elementos do array cuja soma seja o valor). Exemplo:
*
* Input:
* array = 8,7,2,5,3,1
* soma = 10
* Output:
* Par: indices 0 e 2 (8 + 2)
* Par: indices 1 e 4 (7 + 3)
*
* Dica: implemente essa solução em O(n) usando uma tabela hash. Para todos os valores do array, se a chave
* (soma – array[i]) esta no array então os valores da tabela associados a (soma-array[i]) e i são os indices dos
* numeros procurados. Caso contrário, insere o par (sum-array[i],i) no Map.
*/
class ParSoma {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.println("Informe o array de inteiros separados por vírgula:");
String[] array = scanner.nextLine().trim().split(",");
System.out.println("Informe a soma:");
int soma = scanner.nextInt();
int[] numeros = new int[array.length];
for (int i = 0; i < numeros.length; i++) {
numeros[i] = Integer.parseInt(array[i]);
}
encontrarParesSoma(numeros, soma);
}
/**
* Imprime os pares que corresponde a soma.
* @param numeros
* @param soma
*/
static void encontrarParesSoma(int[] numeros, int soma) {
if(numeros.length > 1) {
Map<Integer, Integer> mapa = new HashMap<>();
for (int i = 0; i < numeros.length; i++) {
mapa.put(soma - numeros[i], i);
}
for (int i = 0; i < numeros.length; i++) {
Integer numero1 = mapa.get(soma - numeros[i]);
Integer numero2 = mapa.get(numeros[i]);
if (numero1 != null && numero2 != null && i < numero2) {
System.out.println("Par: indices " + i + " e " + numero2 + " (" + numeros[i] + " + " + numeros[numero2] + ")");
}
}
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment