Força Bruta
1import java.util.HashMap;
2
3 class Solution {
4 public static int[] twoSum(int[] nums, int target) {
5 // 1. Iterate over every possible number pair
6 for (int i = 0; i < nums.length; i++) {
7 // j is always ahead of i so that we don't re-evaluate already evaluated sums
8 for (int j = i + 1; j < nums.length; j++) {
9 // 2. Check if a given pair adds up to our target
10 if (nums[i] + nums[j] == target) {
11 // Return the indices when a pair has been found
12 return new int[]{i, j};
13 }
14 }
15 }
16 // Return an empty array if no pair is found
17 return new int[]{};
18 }
19 }
Análise de Complexidade Temporal/Espaço
-
Complexidade de Tempo:
O(n^2)
, onden
é o tamanho do array. Para cada número, precisamos avaliar todos os outros números do array. -
Complexidade do espaço:
O(1)
, desconsiderando a entrada, todas as outras variáveis têm espaço constante.
Tabela de hash
1import java.util.HashMap;
2
3 class Solution {
4 public static int[] twoSum(int[] nums, int target) {
5 // Our hash table that stores at which index the number is at
6 HashMap<Integer, Integer> numToIndex = new HashMap<>();
7
8 // 1. Iterate over every number in the array
9 for (int i = 0; i < nums.length; i++) {
10 // 2. Calculate the complement that would sum to our target
11 int complement = target - nums[i];
12
13 // 3. Check if that complement is in our hash table
14 if (numToIndex.containsKey(complement)) {
15 return new int[]{numToIndex.get(complement), i};
16 }
17
18 // 4. Add the current number to our hash table
19 numToIndex.put(nums[i], i);
20 }
21
22 // If no solution found, return an empty array
23 return new int[]{};
24 }
25 }
Complexidade de Tempo/Espaço
- Complexidade de Tempo:
O(n)
, onden
é o tamanho do array. Iteramos sobre cada número no array e as operações de consulta/adição da tabela de hash levam um tempo constante. - Complexidade do Espaço:
O(n)
, onden
é o tamanho do array. Nosso mapa de hash armazena todos os números no array de entrada.