Pular para o conteúdo

Two Sum

Aula 2 de 8 · 5 min

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

Qual é a complexidade de tempo do two-sum com hash map?