Two Sum — O(n) with a Hash Map

Use a hash map to store target - nums[i] as we iterate. For each element, check if its complement exists.

def two_sum(nums: list[int], target: int) -> list[int]:
    seen = {}
    for i, n in enumerate(nums):
        if target - n in seen:
            return [seen[target - n], i]
        seen[n] = i
    return []

Time: $O(n)$, Space: $O(n)$.