Hashing: two sum

A hash map (a Python dict) gives you average O(1) lookups. That turns many "have I seen this before?" questions from a slow nested loop into a single fast pass:

seen = {}
seen[7] = 0          # remember: the value 7 lived at index 0
if 7 in seen:        # O(1) — no scanning the list
    seen[7]          # 0

This is LeetCode #1, the classic warm-up. For each number x, its partner is target - x. If you have already seen that partner, you are done — and you stored where you saw it.

Your task

Write two_sum(nums, target) that returns the two distinct 0-based indices [i, j] (with i < j) whose values add up to target. Exactly one solution exists.

two_sum([2, 7, 11, 15], 9)   # [0, 1]   (2 + 7)
two_sum([3, 2, 4], 6)        # [1, 2]   (2 + 4)
two_sum([3, 3], 6)           # [0, 1]

Hint: walk the list once, keeping a dict of value -> index. Before storing the current value, check whether target - value is already in the dict; if so you have found the earlier index.