MiddleCodeVery commonNot answered yet
Two Sum: indices of two numbers summing to a target
Given an array and a target, return the indices of the two numbers that add up to it.
Requirements:
- Assume exactly one valid pair exists; return its two indices.
- You may not use the same element twice.
- Aim for O(n) time, not the O(n²) brute force.
- Return an empty vector if no pair is found.
std::vector<int> twoSum(const std::vector<int>& nums, int target) {
// your code here
}Write the implementation.
Use a hash map from value to index. For each element check whether target - nums[i] is already in the map; if so, return both indices. Otherwise insert nums[i] → i. One pass, O(n) time and O(n) space — versus the O(n²) brute-force double loop.
- ✗Returning the values themselves instead of their indices
- ✗Using the same element twice to form the pair
- ✗Settling for the O(n²) double loop when O(n) is expected
- →How would you adapt this if the input array were already sorted?
- →What changes if there can be multiple valid pairs, or none at all?
Contents
Task
Implement twoSum: return the indices of the two numbers in the array that add up to target, in a single pass.
Solution
std::vector<int> twoSum(const std::vector<int>& nums, int target) {
std::unordered_map<int, int> seen; // value -> index
for (int i = 0; i < static_cast<int>(nums.size()); ++i) {
auto it = seen.find(target - nums[i]);
if (it != seen.end()) return {it->second, i};
seen[nums[i]] = i;
}
return {}; // no pair
}Key points
- Single pass: the complement
target - nums[i]is looked up in O(1) in theunordered_map, so O(n) overall. - Insert
nums[i]after the check — otherwise an element could pair with itself. - The double-loop brute force is also correct but O(n²); the hash map trades space for speed.
Contents
