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.

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
– Incomputable, Commented Jun 2, 2016 at 12:43
@OlzhasZhumabek I thought of that, but std::sort is O(NlogN) while this is O(N) — Dean
– Dean, Commented Jun 2, 2016 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
– Incomputable, Commented Jun 2, 2016 at 12:48
I should try then, no requirements on the size of the vector. — Dean
– Dean, Commented Jun 2, 2016 at 13:33
@SergeyA lookup on a hash map should be O(1) on correct sizing of the buckets. — Andrew Lazarus
– Andrew Lazarus, Commented Jun 4, 2016 at 10:25

coyotte508 · Accepted Answer · 2016-06-02 15:35:53Z

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
– Dean, Commented Jun 2, 2016 at 15:32

Stack Exchange Network

Finding two indices of numbers which sum to N

1 Answer 1

You must log in to answer this question.

Hot Network Questions

Finding two indices of numbers which sum to N

1 Answer 1

You must log in to answer this question.

Related

Hot Network Questions