4Sum

Q: Qual é a complexidade de tempo do 4Sum?

O(n³). Os dois loops selecionam cerca de n²/2 pares (i, j) , e cada um recebe uma varredura de dois ponteiros de no máximo n etapas; a ordenação O(n log n) é pequena em comparação.

Q: Como generalizar 4Sum para kSum?

Escreva kSum(nums, target, k) em uma lista ordenada. Para k = 2, ele executa a varredura com dois ponteiros. Para um k maior, ele percorre o primeiro valor, ignora as repetições e chama a si mesmo com k-1 e target - nums[i] nos valores à direita. Cada nível adiciona um fator de n, então kSum custa O(n^(k-1)).

Q: É possível resolver 4Sum em O(n²)?

Você pode agrupar as n²/2 somas dos pares em um mapa hash e combinar cada par com pares cuja soma seja target menos a soma dele próprio. Isso é rápido quando poucos pares compartilham uma soma, mas uma soma pode conter O(n²) pares, então, no pior caso, não é melhor que O(n³).

MédioDois ponteiros Ordenação

+10

Você recebe uma lista de números inteiros nums e um número inteiro target. Retorne cada quádrupla [a, b, c, d] cujos quatro valores ocupam quatro posições diferentes de nums e somam target. Escreva cada quádrupla com seus valores em ordem não decrescente. Se os mesmos quatro valores puderem ser escolhidos de posições diferentes, a quádrupla ainda deverá aparecer apenas uma vez. Ordene a resposta pelo primeiro valor, depois pelo segundo e, em seguida, pelo terceiro. Se nenhuma quádrupla funcionar, retorne uma lista vazia.

Função

fourSum(nums: integer-array, target: integer) → integer-2d-array

numsinteger-array: os números para escolher, pelo menos um
targetinteger: a soma que cada quarteto deve atingir
Retornainteger-2d-array: os quartetos distintos cuja soma é o alvo, cada um ordenado, e a lista também ordenada; uma lista vazia se não houver nenhum

Restrições

1 ≤ nums.length ≤ 200
-10⁸ ≤ nums[i] ≤ 10⁸
-10⁹ ≤ target ≤ 10⁹
A soma de quaisquer quatro valores fica entre -4 × 10⁸ e 4 × 10⁸, então cabe em um inteiro de 32 bits.
Quartetos que contêm os mesmos quatro valores contam como um só.

Exemplos

Entrada: nums = [3, -1, 0, 2, -2, 1, -3]target = 1
Saída: [[-3, -1, 2, 3], [-3, 0, 1, 3], [-2, -1, 1, 3], [-2, 0, 1, 2]]
Explicação: Cada um dos quatro quartetos soma 1, por exemplo -3 + (-1) + 2 + 3. Os dois que começam com -3 vêm primeiro, ordenados pelo segundo valor: -1 antes de 0.

Entrada: nums = [4, 4, 4, 4, 4, 4]target = 16
Saída: [[4, 4, 4, 4]]
Explicação: As 15 escolhas de quatro posições entre seis resultam em quatro 4s que somam 16, [4, 4, 4, 4] aparece uma vez.

Entrada: nums = [1, 5, 2, 9]target = 3
Saída: []
Explicação: A única opção são os quatro números, e 1 + 5 + 2 + 9 = 17, não 3, então a resposta é uma lista vazia.

Para ir além

Conte os conjuntos de quatro posições cujos valores somam target, em vez das quadras distintas. O segundo exemplo tem 15. Você consegue fazer isso em O(n²)?

Dicas

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

0 de 3 abertas

Solução

Verificar cada conjunto de quatro posições custa O(n⁴), e valores repetidos formam o mesmo quarteto várias vezes. Aplique a redução de 3Sum mais um nível: ordene, fixe os dois primeiros valores com dois loops, encontre o último par com dois ponteiros e ignore valores repetidos em cada nível.

Experimente cada conjunto de quatro

Correta, mas não termina nos maiores testes

Intuição

Primeiro, ordene para que as posições i < j < k < l contenham valores em ordem não decrescente e cada quadrupla seja escrita da maneira correta. Quatro loops aninhados alcançam cada escolha de quatro posições. Para evitar repetições, um loop avança quando a próxima posição contém o valor que ele tentou uma etapa antes. Com seis valores 4, cada loop tenta apenas sua primeira posição, então [4, 4, 4, 4] aparece uma vez em vez de 15 vezes.

Para 200 números, há 64,684,950 conjuntos de quatro, e a contagem cresce cerca de 16 vezes quando n dobra.

Algoritmo

Ordene nums.
Aninhe quatro loops sobre i < j < k < l, cada um começando uma posição depois do loop que o envolve.
Em cada loop, pule uma posição que não seja a primeira do loop e tenha o mesmo valor da posição anterior.
Registre [nums[i], nums[j], nums[k], nums[l]] quando os quatro valores somarem target. Os loops os produzem em ordem crescente.

def fourSum(nums, target):
    nums = sorted(nums)
    n = len(nums)
    quads = []
    for i in range(n - 3):
        if i > 0 and nums[i] == nums[i - 1]:
            continue  # same first value as the round before
        for j in range(i + 1, n - 2):
            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 - 1):
                if k > j + 1 and nums[k] == nums[k - 1]:
                    continue  # same third value as the round before
                for l in range(k + 1, n):
                    if l > k + 1 and nums[l] == nums[l - 1]:
                        continue  # same fourth value as the round before
                    if nums[i] + nums[j] + nums[k] + nums[l] == target:
                        quads.append([nums[i], nums[j], nums[k], nums[l]])
    return quads

Ordenação, dois loops, dois ponteiros

Intuição

Fixe nums[i] e nums[j], e o que resta é uma questão de pares: encontre dois valores à direita de j cuja soma seja igual a target - nums[i] - nums[j]. Em uma lista ordenada, uma única varredura resolve. Comece com lo em j+1 e hi no último índice. Uma soma menor que target move lo para a direita; uma soma maior que ele move hi para a esquerda.

Cada movimento descarta um valor que não faz parte de nenhuma resposta. Se a soma for muito pequena, nem mesmo o maior valor restante, nums[hi], é suficiente para nums[lo], então nums[lo] pode ser descartado. Uma soma muito grande descarta nums[hi] pelo motivo inverso. Um par (i, j) precisa de no máximo n movimentos, então os n²/2 pares custam O(n³).

No primeiro exemplo, com i em -3 e j em -1, lo avança de 0, passando por 1, até 2, onde -3 + (-1) + 2 + 3 = 1.

Algoritmo

Ordene nums.
Para cada i, pule-o quando i > 0 e nums[i] for igual a nums[i-1].
Para cada j após i, pule-o quando j > i+1 e nums[j] for igual a nums[j-1].
Defina lo = j+1 e hi = n-1. Enquanto lo < hi, compare a soma dos quatro valores com target: se for menor, mova lo para a direita; se for maior, mova hi para a esquerda.
Ao encontrar uma correspondência, registre a quadrupla, mova os dois ponteiros e, em seguida, avance lo enquanto ele mantiver o valor que usou.

def fourSum(nums, target):
    nums = sorted(nums)
    n = len(nums)
    quads = []
    for i in range(n - 3):
        if i > 0 and nums[i] == nums[i - 1]:
            continue  # this first value was already handled
        for j in range(i + 1, n - 2):
            if j > i + 1 and nums[j] == nums[j - 1]:
                continue  # this second value was already handled
            lo, hi = j + 1, n - 1
            while lo < hi:
                total = nums[i] + nums[j] + nums[lo] + nums[hi]
                if total < target:
                    lo += 1
                elif total > target:
                    hi -= 1
                else:
                    quads.append([nums[i], nums[j], nums[lo], nums[hi]])
                    lo += 1
                    hi -= 1
                    while lo < hi and nums[lo] == nums[lo - 1]:
                        lo += 1
    return quads

Armadilhas e casos extremos

Pular j sempre que nums[j] for igual a nums[j-1]. Em j = i+1, esse valor é comparado com o valor usado por i, então [2, 2, 2, 2, 2] com alvo 8 perde [2, 2, 2, 2].
Copiar a saída antecipada do 3Sum nums[i] > target. Com [-5, -4, -3, -2, -1] e alvo -10, o loop para em -5 e não encontra [-4, -3, -2, -1].
Listas com menos de quatro elementos. Com um ou dois números, n-3 é negativo: 0..<(n - 3) causa um erro em Swift, e n - 3 em um usize do Rust sofre underflow. Retorne primeiro uma lista vazia.
Armazenar as quadras em um conjunto hash e retorná-las sem ordenação.

Perguntas frequentes3

Qual é a complexidade de tempo do 4Sum?

O(n³). Os dois loops selecionam cerca de n²/2 pares (i, j), e cada um recebe uma varredura de dois ponteiros de no máximo n etapas; a ordenação O(n log n) é pequena em comparação.

Como generalizar 4Sum para kSum?

Escreva kSum(nums, target, k) em uma lista ordenada. Para k = 2, ele executa a varredura com dois ponteiros. Para um k maior, ele percorre o primeiro valor, ignora as repetições e chama a si mesmo com k-1 e target - nums[i] nos valores à direita. Cada nível adiciona um fator de n, então kSum custa O(n^(k-1)).

É possível resolver 4Sum em O(n²)?

Você pode agrupar as n²/2 somas dos pares em um mapa hash e combinar cada par com pares cuja soma seja target menos a soma dele próprio. Isso é rápido quando poucos pares compartilham uma soma, mas uma soma pode conter O(n²) pares, então, no pior caso, não é melhor que O(n³).

def fourSum(nums, target):
    # Escreva o código aqui

Teste #1

Teste #2

Teste #3

Argumentos

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

Saída Esperada

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