Two Sum
LeetCode #1 · Easy · Arrays · C++ solution with worked-out approach and complexity analysis.
Approach
Hash Map
Use a hash map to store each number and its index as we iterate. For each number, check if (target - num) exists in the map.
Time
O(n)
single pass through the array
Space
O(n)
hash map stores at most n elements
Problem description(from LeetCode)
Given an array of integers nums and an integer target, return 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.
Examples
Example 1
- Input:
- nums = [2,7,11,15], target = 9
- Output:
- [0,1]
- Note:
- Because nums[0] + nums[1] == 9, we return [0, 1].
Constraints
- •2 <= nums.length <= 10^4
- •-10^9 <= nums[i] <= 10^9
- •-10^9 <= target <= 10^9
- •Only one valid answer exists.
C++ Solution
solution.cpp
class Solution {
public:
vector<int> twoSum(vector<int> &nums, int target) {
unordered_map<int, int> seen; // num -> index
for (int i = 0; i < nums.size(); i++) {
int complement = target - nums[i];
if (seen.find(complement) != seen.end()) {
return {seen[complement], i};
}
seen[nums[i]] = i;
}
return {}; // No solution found (shouldn't happen per constraints)
}
};