Two Sum
The **Two Sum** problem is one of the most famous and fundamental algorithms. Given an array of integers `nums` and an integer `target`, return the indices of the two numbers such that they add up to `target`.
You may assume that each input would have **exactly one solution**, and you may not use the same element twice.
### How it works (Hash Map approach): While a brute-force approach (checking every pair) takes `O(n²)` time, we can optimize this to `O(n)` using a Hash Map (or Dictionary): 1. Create an empty Hash Map to store elements we've seen: `{ value: index }`. 2. Iterate through the array. For each element `num`, calculate its required `complement` (`target - num`). 3. If the `complement` exists in our Hash Map, we have found our pair! Return the current index and the index of the complement from the map. 4. If not, add the current `num` and its index to the Hash Map and continue.
You may assume that each input would have **exactly one solution**, and you may not use the same element twice.
### How it works (Hash Map approach): While a brute-force approach (checking every pair) takes `O(n²)` time, we can optimize this to `O(n)` using a Hash Map (or Dictionary): 1. Create an empty Hash Map to store elements we've seen: `{ value: index }`. 2. Iterate through the array. For each element `num`, calculate its required `complement` (`target - num`). 3. If the `complement` exists in our Hash Map, we have found our pair! Return the current index and the index of the complement from the map. 4. If not, add the current `num` and its index to the Hash Map and continue.
Constraints
- 2 <= nums.length <= 10^4
- -10^9 <= nums[i] <= 10^9
- -10^9 <= target <= 10^9
- Only one valid answer exists.
TimeO(O(n))
SpaceO(O(n))
Ready to startStep 0 / 0
TypeScript