Two Sum
Easy · rating 900 · arrays, hashing
The classic Two Sum problem. The first line contains n and a target t. The second line contains n integers. Print the 0-indexed positions of the two numbers that add up to t, separated by a space (any valid pair if multiple exist). If none exists, print -1 -1.
Constraints: 2 ≤ n ≤ 105
Editorial
Approach
The brute-force solution checks every pair of numbers in O(n²) time. We can do better with a hash map. As we scan the array once, for each value x we ask: have we already seen its complement target − x? If so, we've found the pair; if not, we record x and its index and move on.
Why it works
By storing each number's index as we go, the complement lookup is O(1), so a single pass answers the question. Because we check for the complement before inserting the current element, we never pair an element with itself.
seen = {}
for i, x in enumerate(nums):
if target - x in seen:
return [seen[target - x], i]
seen[x] = iComplexity
Time: O(n) — one pass. Space: O(n) for the hash map.