awelgorithms

Two Sum: the skills you need first

Updated

LeetCode · easy · hash maps. One pass: store what you have seen, query the complement.

open on LeetCode

Skills this problem builds on

Stuck on Two Sum? It is usually one of these. Get each one solid and the solution stops being a trick.

  1. Two-sum with a value-to-index map

    Scan left to right. At j, if target−a[j] is a key with index i≠j, return (i,j). Then put a[j]→j (usually last-index / overwrite). One pass, expected O(n).

  2. Check whether a map contains a key

    contains-key / has-key is a membership test on the key set. It does not look at values. It is expected O(1), the same hash as get.

  3. Get the value for a key

    Get hashes the key, walks that bucket, and returns the stored value if the key is present. It does not scan other keys. It does not search by value.

check which ones you have 10 minutes, free, no account.

More hash maps problems