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&lt;int&gt; twoSum(vector&lt;int&gt;&amp; nums, int target) {
    unordered_multimap&lt;int, int&gt; numbers_multimap;
    numbers_multimap.reserve(nums.size());
    for(size_t i = 0; i &lt; 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-&gt;second;
            if (other_position != i)
                return vector&lt;int&gt;{i, other_position};
        }
    }
    return vector&lt;int&gt;{};
}


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.
You can emplace after testing for the complementary, it simplifies the code and avoids using a multimap:

vector&lt;int&gt; twoSum(vector&lt;int&gt;&amp; nums, int target) {
    unordered_map&lt;int, int&gt; 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 &lt; nums.size(); ++i) {
        int num = nums[i];
        if (num &gt; 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-&gt;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&lt;int&gt; 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.