Conteúdo do curso Lição 55 de 148 · Velocidade sem o cache
Velocidade sem o cache

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.

O serviço

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)
Sua vez

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.