Two sum with a dictionary

Find two numbers that add up to a target in an unsorted array, in a single pass.

Time O(n)Space O(n)Code C++, Python and C#

Watch it animatedStep through it, with the running line highlighted. Free with an account.

The idea

For each number, the partner it needs is target minus itself. A dictionary of everything seen so far answers "have I met my partner?" in constant time.

Code

C++PythonC#

vector<int> twoSum(const vector<int>& a, int target) {
    unordered_map<int, int> seen; // value -> index
    for (int i = 0; i < (int)a.size(); i++) {
        int need = target - a[i];
        if (seen.count(need)) return {seen[need], i};
        seen[a[i]] = i;
    }
    return {};
}

def two_sum(a: list[int], target: int) -> list[int]:
    seen = {}  # value -> index
    for i, x in enumerate(a):
        need = target - x
        if need in seen: return [seen[need], i]
        seen[x] = i
    return []

public static int[] TwoSum(int[] a, int target) {
    var seen = new Dictionary<int, int>(); // value -> index
    for (int i = 0; i < a.Length; i++) {
        int need = target - a[i];
        if (seen.TryGetValue(need, out int j)) return new[] { j, i };
        seen[a[i]] = i;
    }
    return Array.Empty<int>();
}

Tips

Check for the partner before adding the current number, so a value is never paired with itself.
This is the standard move: replace an inner loop with a hash lookup.

In the .NET library

Dictionary<TKey,TValue> gives average O(1) add and lookup. Use HashSet<T> when you only need to know whether a value exists.