3Sum

+10

Você recebe uma lista de números inteiros nums. Encontre cada trinca [a, b, c] de valores obtidos de três posições diferentes de nums, de modo que a + b + c = 0. Escreva cada trinca em ordem não decrescente (a ≤ b ≤ c) e liste cada trinca distinta uma única vez, mesmo quando várias escolhas de posições a produzirem. Retorne as trincas ordenadas pelo primeiro valor e, em seguida, pelo segundo.

Função

threeSum(nums: integer-array) → integer-2d-array

numsinteger-array: a lista de números inteiros, com pelo menos três elementos
Retornainteger-2d-array: cada trio distinto cuja soma seja 0, cada um em ordem não decrescente, a lista ordenada

Restrições

3 ≤ nums.length ≤ 3000
-10⁵ ≤ nums[i] ≤ 10⁵
Pelo menos uma trinca soma 0.
Dois trios são iguais quando contêm os mesmos três valores.

Exemplos

Entrada: nums = [-2, 0, 1, 1, -1, 2]
Saída: [[-2, 0, 2], [-2, 1, 1], [-1, 0, 1]]
Explicação: -2 + 0 + 2, -2 + 1 + 1 e -1 + 0 + 1 resultam em 0. [-2, 1, 1] pode usar o valor 1 duas vezes porque 1 está em duas posições, enquanto [-1, 0, 1] pode ser formado usando qualquer um dos valores 1, mas aparece uma vez.

Entrada: nums = [0, 0, 0, 0]
Saída: [[0, 0, 0]]
Explicação: Quaisquer três dos quatro zeros somam 0. Isso dá quatro escolhas de posições, mas todas resultam na mesma trinca, então a resposta inclui [0, 0, 0] uma única vez.

+15 testes ocultos ao enviar

Para ir além

O mesmo padrão resolve o 4Sum: fixe dois valores e use dois ponteiros no restante. Você consegue escrevê-lo em O(n³) e manter as regras para duplicatas corretas em todos os níveis?

Dicas

Abra uma de cada vez. Cada uma revela um pouco mais.

0 de 3 abertas

Solução

Duas coisas tornam o 3Sum mais difícil do que parece. Verificar cada trio custa O(n³), e a resposta deve conter cada trinca apenas uma vez, mesmo quando há valores repetidos. A ordenação resolve os dois problemas: valores iguais ficam lado a lado, então você pode pular repetições comparando os vizinhos; e, depois que o menor valor é fixado, os outros dois formam um problema de soma de pares em uma lista ordenada, que dois ponteiros resolvem em uma única passagem.

Experimente todos os trios

Correta, mas não termina nos maiores testes

Intuição

Ordene a lista primeiro. Então, quaisquer três posições i < j < k fornecem valores que já estão em ordem, nums[i] ≤ nums[j] ≤ nums[k], então uma trinca é escrita corretamente assim que você a encontra. Três loops aninhados percorrem todas as escolhas de posições, portanto nenhuma trinca pode ser perdida.

Agora vêm as repetições. O primeiro exemplo ordenado é [-2, -1, 0, 1, 1, 2], e [-1, 0, 1] pode usar o 1 do índice 3 ou do índice 4. Portanto, cada loop ignora uma posição cujo valor seja igual ao valor que esse mesmo loop tentou antes. Cada loop então tenta cada valor distinto uma vez, e cada trinca distinta aparece uma vez, já em ordem crescente. O salto só compara com a posição anterior dentro do mesmo loop, então [-2, 1, 1] ainda usa os dois uns.

O problema é o custo. Existem cerca de n³/6 trios: para 3000 números, são 4.5 × 10^9 somas, muito além de qualquer limite de tempo.

Algoritmo

Ordene nums.
Percorra as posições com i e ignore i quando nums[i] for igual a nums[i-1].
Dentro desse loop, percorra j a partir de i+1 e ignore j quando j > i+1 e nums[j] for igual a nums[j-1].
Dentro desse loop, percorra k a partir de j+1, usando a mesma regra para ignorar, e registre [nums[i], nums[j], nums[k]] quando os três somarem 0.
Retorne as trincas na ordem em que as encontrou. Elas já estão ordenadas.

def threeSum(nums):
    nums = sorted(nums)
    n = len(nums)
    triplets = []
    for i in range(n - 2):
        if i > 0 and nums[i] == nums[i - 1]:
            continue  # same first value as the round before
        for j in range(i + 1, n - 1):
            if j > i + 1 and nums[j] == nums[j - 1]:
                continue  # same second value as the round before
            for k in range(j + 1, n):
                if k > j + 1 and nums[k] == nums[k - 1]:
                    continue  # same third value as the round before
                if nums[i] + nums[j] + nums[k] == 0:
                    triplets.append([nums[i], nums[j], nums[k]])
    return triplets

Fixe um valor, encontre o par usando um conjunto hash

Intuição

Depois que o primeiro valor nums[i] é fixado, você precisa de dois valores posteriores cuja soma seja -nums[i]. Isso é Two Sum. Percorra j à direita de i e mantenha um conjunto dos valores pelos quais você passou. Para cada j, o valor que falta é need = -nums[i] - nums[j]. Se need estiver no conjunto, [nums[i], need, nums[j]] soma 0. Uma busca em conjunto custa O(1) em média, então um i custa O(n) e a busca inteira, O(n²).

A ordenação ainda faz o trabalho de controle. Ignore um i cujo valor seja igual ao anterior. Depois de uma correspondência, avance j além de todas as cópias de nums[j]: com o primeiro e o terceiro valores fixados, o do meio também está fixado, então outra cópia só poderia repetir a mesma trinca. Como need vem de uma posição anterior da lista ordenada, need ≤ nums[j] e a trinca está em ordem. Você também pode parar assim que nums[i] > 0: os dois valores seguintes são pelo menos tão grandes quanto ele, então a soma não pode chegar a 0.

Um detalhe: conforme j avança para a direita, nums[j] aumenta e need diminui, então as trincas para um mesmo i aparecem com o valor do meio diminuindo. Em [-2, -1, 0, 1, 1, 2] com i = 0, você encontra [-2, 1, 1] no segundo 1 e depois [-2, 0, 2] no 2. Inverta cada grupo antes de adicioná-lo à resposta. As versões em C e R marcam os valores vistos em um array indexado pelo valor, em vez de usar um conjunto hash, o que funciona porque todos os valores estão no intervalo de ±10^5.

Algoritmo

Ordene nums.
Para cada i, pare quando nums[i] > 0 e pule i quando nums[i] for igual a nums[i-1].
Comece com um conjunto vazio. Para cada j a partir de i+1, calcule need = -nums[i] - nums[j]. Se need estiver no conjunto, registre [nums[i], need, nums[j]] e avance j além das cópias de nums[j].
Adicione nums[j] ao conjunto e passe para o próximo j.
Inverta as trincas encontradas para este i e acrescente-as à resposta.

def threeSum(nums):
    nums = sorted(nums)
    n = len(nums)
    triplets = []
    for i in range(n - 2):
        if nums[i] > 0:
            break  # the two values after it are at least as large
        if i > 0 and nums[i] == nums[i - 1]:
            continue  # this first value was already handled
        group = []
        seen = set()  # values between position i and position j
        j = i + 1
        while j < n:
            need = -nums[i] - nums[j]
            if need in seen:
                group.append([nums[i], need, nums[j]])
                while j + 1 < n and nums[j + 1] == nums[j]:
                    j += 1
            seen.add(nums[j])
            j += 1
        # need shrinks as nums[j] grows, so this group came out backwards
        group.reverse()
        triplets.extend(group)
    return triplets

Ordene e use dois ponteiros

Intuição

A ordem ordenada pode substituir o conjunto. Fixe nums[i], coloque lo em i+1 e hi no último índice, e observe nums[i] + nums[lo] + nums[hi]. Se o resultado for menor que 0, você precisa de um valor maior, então lo avança para a direita. Se for maior que 0, você precisa de um menor, então hi recua para a esquerda. Se for exatamente 0, registre a trinca e mova ambos.

Nenhuma trinca é perdida. Quando a soma é menor que 0, nums[lo] ainda é insuficiente mesmo com o maior valor restante, nums[hi], então não pode formar um par com nada que ainda esteja no intervalo, e descartá-lo não causa nenhuma perda. O caso acima de 0 é o inverso: nums[hi] é grande demais mesmo com o menor valor restante. Cada etapa descarta definitivamente um valor, então um i custa no máximo n etapas e a busca inteira custa O(n²), sem usar memória além da ordenação e da saída.

Considere a lista ordenada [-2, -1, 0, 1, 1, 2]. Com i = 0 (valor -2), lo começa em -1 e hi em 2: a soma é -1, então lo avança para 0. Agora, -2 + 0 + 2 = 0, então você registra [-2, 0, 2] e os dois ponteiros chegam aos dois valores 1, que formam [-2, 1, 1]. Com i = 1 (valor -1), 0 e 2 resultam em 1, então hi recua para o segundo valor 1, e -1 + 0 + 1 = 0 registra [-1, 0, 1]. O valor 0 em i = 2 não encontra nada, e em i = 3 o valor é positivo, então a busca termina.

Para valores repetidos, são necessárias duas regras. Ignore um i cujo valor seja igual ao anterior. Depois de encontrar uma combinação, avance lo para além das cópias do valor que ele usou. hi não precisa de uma regra própria: com lo em um valor maior, uma cópia do antigo nums[hi] agora produz uma soma maior que 0 e se afasta por conta própria. Como i percorre os valores distintos em ordem crescente e lo só avança para a direita, as trincas são geradas em ordem crescente.

Algoritmo

Ordene nums.
Para cada i, pare quando nums[i] > 0 e ignore i quando nums[i] for igual a nums[i-1].
Defina lo = i+1 e hi = n-1. Enquanto lo < hi, some nums[i], nums[lo] e nums[hi].
Se a soma for menor que 0, mova lo para a direita. Se for maior que 0, mova hi para a esquerda.
Se for 0, registre a trinca, mova os dois ponteiros e, em seguida, avance lo além das cópias do valor usado.
Retorne as trincas. Elas já estão ordenadas.

def threeSum(nums):
    nums = sorted(nums)
    n = len(nums)
    triplets = []
    for i in range(n - 2):
        if nums[i] > 0:
            break  # the two values after it are at least as large
        if i > 0 and nums[i] == nums[i - 1]:
            continue  # this first value was already handled
        lo, hi = i + 1, n - 1
        while lo < hi:
            total = nums[i] + nums[lo] + nums[hi]
            if total < 0:
                lo += 1
            elif total > 0:
                hi -= 1
            else:
                triplets.append([nums[i], nums[lo], nums[hi]])
                lo += 1
                hi -= 1
                while lo < hi and nums[lo] == nums[lo - 1]:
                    lo += 1
    return triplets

Armadilhas e casos extremos

A maioria das respostas incorretas decorre de valores repetidos, então teste com entradas que os contenham.

Ignorar i quando nums[i] é igual a nums[i+1] mantém a última cópia de cada valor como o primeiro elemento, e as cópias anteriores a ela desaparecem. Em [-1, -1, 2], isso perde [-1, -1, 2]. Compare com a posição anterior, nums[i-1].
Parar quando nums[i] ≥ 0 em vez de nums[i] > 0 faz com que [0, 0, 0] não seja considerado.
Remover as repetições no final em vez de ignorá-las. Com 3000 zeros, o loop de dois ponteiros registra milhões de cópias de [0, 0, 0] antes de qualquer limpeza e, em várias linguagens, um conjunto de listas compara as listas por identidade, então as cópias acabam permanecendo de qualquer forma.
Usar a mesma posição duas vezes. Uma versão com hash set que preenche o conjunto com a lista inteira logo no início transforma [-2, 1, 3] em [-2, 1, 1] ao usar o único 1 duas vezes. Consulte apenas os valores nas posições pelas quais você já passou.
Retornar os trios fora de ordem. A comparação é exata, então a versão com hash set precisa inverter cada grupo, e uma solução que coleta trios em um conjunto precisa ordená-los no final.

Perguntas frequentes4

Qual é a complexidade de tempo do 3Sum?

A solução de ordenação e dois ponteiros tem complexidade de tempo O(n²). A ordenação custa O(n log n), e cada uma das n escolhas do primeiro valor exige uma varredura de O(n). Ela precisa de O(1) de espaço extra, além do necessário para a ordenação e a saída. Verificar cada trio exige O(n³), em vez disso.

Como o 3Sum evita tripletos duplicados?

Ele ordena a lista, fazendo com que valores iguais fiquem lado a lado. Em seguida, ignora um valor inicial que seja igual ao anterior e, após cada correspondência, move o ponteiro esquerdo para além das cópias do valor utilizado. Cada trio é encontrado uma única vez, a partir das primeiras cópias de seus valores, portanto não é necessário usar um conjunto de resultados.

Devo usar dois ponteiros ou um conjunto hash para 3Sum?

Ambos executam em tempo O(n²). Dois ponteiros não precisam de memória extra, e a ordenação coloca as trincas em ordem. Um conjunto hash consome O(n) de memória e exige cuidado para manter as posições distintas e a saída ordenada. A ideia do conjunto hash é importante quando você não pode ordenar, como no Two Sum, em que você retorna os índices originais.

É possível resolver o 3Sum mais rápido que O(n²)?

Não muito. Os algoritmos mais conhecidos superam n² apenas por alguns fatores logarítmicos, e muitos resultados de dificuldade em geometria computacional pressupõem que nenhum algoritmo alcance uma potência de n inferior a 2. Esses algoritmos mais rápidos são resultados de pesquisa, então O(n²) é a resposta esperada em entrevistas.

Python

def threeSum(nums):
    # Escreva o código aqui

Casos de teste

Caso 1

Caso 2

Entrada

nums = [-2, 0, 1, 1, -1, 2]

Esperado

[[-2, 0, 2], [-2, 1, 1], [-1, 0, 1]]

3Sum

Função

Restrições

Exemplos

Dicas

Solução

Experimente todos os trios

Fixe um valor, encontre o par usando um conjunto hash

Ordene e use dois ponteiros

Armadilhas e casos extremos

Perguntas frequentes4

Problemas parecidos