O hash map (dicționar) oferă O(1) în medie pentru căutări, inserări și ștergeri. Tranzacționând memoria O(n) pentru viteză, mulți algoritmi O(n²) se transformă în O(n) prin înlocuirea scanărilor repetate cu căutări instantanee.
Ideea
În loc să cauți o listă de fiecare dată, stochează valorile pe care le-ai văzut într-o hash map și verifică apartenența în timp constant.
Exemplu: two-sum în O(n)
():
seen = {}
i, x (nums):
need = target - x
need seen:
(seen[need], i)
seen[x] = i
two_sum([, , , ], )
