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.

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.