Executando verificação de segurança...
1

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;
}
Carregando publicação patrocinada...
1

Que massa!!! Até a leitura do código ficou muito melhor seguindo a técnica do i + 1 que você apresentou.

Admito que eu não sabia que em Big O eu deveria "arredondar" para a grandeza mais próxima, realmente muito bacana todo esse conhecimento a respeito da complexidade dos algoritmos, principalmente visando construir algoritmos cada vez mais eficientes, mas também para compreender como os algortimos que já temos funciona e como podemos melhorar eles. Tem sido extremamente interessante estudar esta área da computação e tenho ficado cara vez mais maravilhado com seus conceitos e regras.

Você realmente me ajudou um monte! E o artigo na Wiki que você sitou é realmente uma leitura muito massa pra quem tá querendo entender o que exatamente e o Big O. Realmente espetacular!

1