Finding two indices of numbers which sum to N

Question

I'm solving some online puzzles and I had this problem:

Given a vector, write code to find the indices of TWO values which sum to a given number N

so if I'm given [2, 5, 6] and N = 8, I should output the 0-based indices [0, 2].

I wrote the following code to do this in O(N)

vector<int> twoSum(vector<int>& nums, int target) {
 unordered_multimap<int, int> numbers_multimap;
 numbers_multimap.reserve(nums.size());
 for(size_t i = 0; i < nums.size(); ++i) {
 numbers_multimap.emplace(nums[i], i);
 auto interval = numbers_multimap.equal_range(target - nums[i]);
 for (auto it = interval.first; it != interval.second; ++it) {
 int other_position = it->second;
 if (other_position != i)
 return vector<int>{i, other_position};
 }
 }
 return vector<int>{};
}

and it works, but I noticed that there are faster solutions.

Since I suppose the algorithm is already quite fast, I'd like to know if there are additional pro tips to improve the runtime of this code.

• Incomputable: I think it would be better to sort vector, start from the beginning and search N - nums[i] using binary search. What is maximum size of the vector?
• Dean: @OlzhasZhumabek I thought of that, but std::sort is O(NlogN) while this is O(N)
• Incomputable: have you benchmarked it? big O is algorithmic complexity, but things as memory aliasing, cache consistency can throw that complexity in trash bin
• Dean: I should try then, no requirements on the size of the vector.
• Andrew Lazarus: @SergeyA lookup on a hash map should be O(1) on correct sizing of the buckets.

Answer 1

You can emplace after testing for the complementary, it simplifies the code and avoids using a multimap:

vector<int> twoSum(vector<int>& nums, int target) {
 unordered_map<int, int> numbers;
 //removed because can be very inefficient if nums is big or there are a lot of duplicates
 //numbers.reserve(nums.size());
 //a micro optimization could be to loop from the back and compare
 // i to 0 in the test but it doesn't weigh much against container operations
 for(size_t i = 0; i < nums.size(); ++i) {
 int num = nums[i];
 if (num > target) {
 continue; //no need to waste time storing it either, assuming all numbers are unsigned
 }
 auto it = numbers.find(target - num);
 if (it != numbers.end()) {
 return {i, it->second};
 }
 //no need to emplace for integers? actually slower than insert if key is already present
 numbers.insert({num, i});
 }
 return {};
}

If the values are in a range comparable to the size of the vector, you can just create a valarray<int> of size maxValue+1, fill it to -1 on initialization, and use that instead of the map to check if a value is already present.

Another small optimization that can be done would be to have your loop like that:

int i = 0;
for (int num : nums) {
 //...
 //calls to 'continue' can be replaced by goto endloop
endloop: 
 i++; //equivalent in performance to ++i for basic types
}

Iterating over the container like this (which is actually moving a pointer forward) is faster than accessing the element of the vector by its index every time. Although it's a relatively small optimization given that there are map operations used in the loop itself.

• Dean: I don't think I can loop this way: for (int num : nums[i]), an integer has no begin function
• coyotte508: @Dean sorry, fixed, removed the [i]