O getTwoSum
tem complexidade O(n2). Lembre-se que a notação Big-O é assintótica (de forma bem resumida, é como se você "arredondasse" para a grandeza mais próxima). E como vc faz dois loops aninhados no mesmo array, na prática é quadrático. Mesmo que o loop interno não percorra todos os elementos, o valor será mais próximo do quadrático do que do linear (considerando valores grandes, já que Big-O define o "limite quando N tende ao infinito").
Vale contar que cada chamada de slice
percorre um trecho do array novamente, para poder criar outro (ou seja, vc está criando vários arrays, um novo a cada iteração de index_1
). Quer dizer que para cada elemento, vc cria um novo sub-array e depois faz um loop no array retornado. Então para cada elemento, é como se vc percorresse o array duas vezes: uma para o slice
criar outro array, e outra para percorrer os elementos do array que slice
retornou (n * 2n, ou seja, 2n2), mas como a notação é assintótica, continua sendo O(n2).
Enfim, não precisa de slice
, pois não há motivo para copiar parte do array. Afinal em nenhum momento vc modifica o array (que seria um motivo válido para fazer a cópia, por exemplo), e não há problema nenhum se os dois loops usarem o mesmo array. Ou seja, pode fazer o loop interno no mesmo array, basta começar no i + 1
:
function getTwoSum(numbers, target_sum) {
for (let i = 0; i < numbers.length - 1; i++) {
for (let j = i + 1; j < numbers.length; j++) {
if (numbers[i] + numbers[j] === target_sum) {
return [numbers[i], numbers[j]];
}
}
}
return [];
}
Note que depois das }
não precisa de ponto-e-vírgula.
Claro, continua sendo quadrático, mas agora com menos iterações, porque sem slice
não há a criação de novos arrays (agora é n2 em vez de 2n2, mas ainda sim, a complexidade continua sendo O(n2)).
Da mesma forma, getThreeSum
é O(n3), e não precisa de slice
, pois com isso vc cria vários arrays desnecessariamente. Outra diferença é que no getTwoSum
vc retorna assim que encontra um caso que sirva, enquanto no getThreeSum
vc guarda todas as combinações possíveis, além de ordenar o resultado (mas pelo que entendi, era essa a intenção).
E outro detalhe é que vc chama sort
em um array de números, mas assim ele não ordena corretamente, porque primeiro ele converte os números para string e a ordenação fica errada (faça o teste, rode console.log([3, 10, 2].sort())
pra ver o que acontece). Então precisa de um pequeno ajuste:
function getThreeSum(numbers, target_sum) {
const result = [];
for (let i = 0; i < numbers.length - 2; i++) {
for (let j = i + 1; j < numbers.length - 1; j++) {
for (let k = j + 1; k < numbers.length; k++) {
if (numbers[i] + numbers[j] + numbers[k] === target_sum) {
// sort: para ordenar de acordo com o valor numérico, precisa desta função de callback
result.push([numbers[i], numbers[j], numbers[k]].sort((a, b) => a - b));
}
}
}
}
return result;
}
E só para constar, existem algoritmos para reduzir getTwoSum
para O(n) e getThreeSum
para O(n2) (retirados respectivamente daqui e daqui):
function getTwoSum(numbers, target_sum) {
let hashMap = {};
for (let i = 0; i < numbers.length; i++) {
if (hashMap[numbers[i]]) {
return [hashMap[numbers[i]], numbers[i]];
} else {
hashMap[target_sum - numbers[i]] = numbers[i];
}
}
return [];
}
function getThreeSum(numbers, target_sum) {
const result = [];
for (let i = 0; i < numbers.length - 2; i++) {
// verifica no intervalo [i+1..n-1] se existe uma soma igual a target_sum - numbers[i]
let s = new Set(); // usa um Set, que é O(1) para buscas
let curr_sum = target_sum - numbers[i];
for (let j = i + 1; j < numbers.length; j++) {
if (s.has(curr_sum - numbers[j])) { // em um Set, a busca é O(1)
result.push([numbers[i], numbers[j], curr_sum - numbers[j]].sort((a, b) => a - b));
}
s.add(numbers[j]);
}
}
return result;
}
Ou, se quiser que getTwoSum
retorne todas as possibilidades:
function twoSum(numbers, target_sum) {
let hashMap = {}, results = [];
for (let i = 0; i < numbers.length; i++) {
if (hashMap[numbers[i]]) {
results.push([hashMap[numbers[i]], numbers[i]].sort((a, b) => a - b));
} else {
hashMap[target_sum - numbers[i]] = numbers[i];
}
}
return results;
}