Dois ponteiros, sem tabela
Por que isso importa "Encontre duas coisas que somam X" tem uma resposta selada famosa: coloque tudo em um set e procure o par. É rápido, e precisa de uma cópia de todos os dados. Quando os dados estão ordenados, você quase não precisa de memória.
A vende pacotes de dois produtos diferentes por um preço de pacote fixo. A lista de preços dos produtos está ordenada, não tem repetições e fica em um dispositivo embarcado com pouquíssima memória livre. Para um preço de pacote, você precisa do número de pares de produtos cujos preços somam exatamente esse preço.
prices = [1, 2, 3, 4, 5, 6] # sorted, no repeats
count_pairs(Tape(prices), 7) # 3: (1, 6), (2, 5), (3, 4)Escreva count_pairs(tape, target). tape é uma Tape de preços de números inteiros, ordenados de forma crescente, sem repetições. Retorne quantos pares de dois itens diferentes somam exatamente target (cada par contado uma vez). Budgets: para 20.000 itens lendo no máximo 60.000 valores, e use no máximo 16.000 bytes de memória de trabalho enquanto sua function roda (medido com tracemalloc; um set ou list de 20.000 preços é maior que 150.000 bytes). len(tape) é grátis.
Viu um problema nesta lição? Reporte-o · Pergunte sobre esta lição
Este exercício abre em breve
Termine a lição anterior para que esta seja desbloqueada. O curso inteiro é gratuito, não precisa de conta, e você pode ler esta lição agora mesmo.
Este navegador está bloqueando cookies para learn.floati.life, então as lições que você terminou aqui não podem abrir em ordem. Permita cookies para este site e recarregue.