Two Sum
Passo 1 de 8
Checar cada par é O(n²). Em vez disso, percorra uma vez e lembre do que já passou.
A ideia
Comparar todos os pares custa O(n²). Em vez disso, percorra a lista uma vez e faça uma só pergunta a um dicionário de valores já vistos: o complemento — o alvo menos este valor — já passou? A busca no hash responde na hora, então uma única passada resolve.
Exemplo do mundo real
Uma loja de material de construção tem uma caixa de sobras de madeira, e um cliente precisa de exatamente 240 cm com duas peças. O atendente mede cada sobra uma vez, anota os comprimentos num bloco e, depois de cada medida, olha o bloco atrás da medida que falta, em vez de vasculhar a caixa de novo.
O código
Sua vez
Preencha a lacuna.
def two_sum(nums, target):
seen = {}
for i, x in enumerate(nums):
if ___ in seen:
return (seen[target - x], i)
seen[x] = i
print(two_sum([90, 40, 200, 40], 240)) # want (1, 2)Mini quiz
1 / 3