Last active
October 20, 2018 22:58
Star
You must be signed in to star a gist
➕ Dado um array de inteiros nao ordenado, encontrar o par cuja soma é um dado valor.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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