Two Sum
Given an array of integers `nums` and an integer `target`, return the indices of the two numbers that add up to `target`. You are guaranteed exactly one solution exists, and you cannot use the same element twice. **Core Insight:** A brute-force approach checks every pair in O(n²). The optimal solution uses a hash map to store each number's index as we iterate. For every element `nums[i]`, we compute its complement `target - nums[i]` and check if that complement already exists in the map. If it does, we immediately return both indices. If not, we store `nums[i]` → `i` and move on. **Algorithm:** Single-pass hash map. For each element, look up its complement in O(1). Store the element if the complement is not found yet. **Complexity:** Time O(n) — one pass through the array. Space O(n) — the hash map stores at most n entries.
Constraints
- •
2 ≤ nums.length ≤ 10⁴ - •
-10⁹ ≤ nums[i] ≤ 10⁹ - •
Only one valid answer exists
def twoSum(nums: list[int], target: int) -> list[int]:
seen = {}
for i, num in enumerate(nums):
complement = target - num
if complement in seen:
return [seen[complement], i]
seen[num] = i
return []