# Finding two indices of numbers which sum to N

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.

• 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? – Incomputable Jun 2 '16 at 12:43
• @OlzhasZhumabek I thought of that, but std::sort is O(NlogN) while this is O(N) – Dean Jun 2 '16 at 12:44
• have you benchmarked it? big O is algorithmic complexity, but things as memory aliasing, cache consistency can throw that complexity in trash bin – Incomputable Jun 2 '16 at 12:48
• I should try then, no requirements on the size of the vector. – Dean Jun 2 '16 at 13:33
• @SergeyA lookup on a hash map should be O(1) on correct sizing of the buckets. – Andrew Lazarus Jun 4 '16 at 10:25

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.

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