Finding sum in an array

Question

I have this program finding 2 numbers in the array (unsorted) so that its sum equal to the target sum. Here is my program:

vector<int> findNumbers(vector<int>& nums, int target) { vector<int> result; for(int i = 0; i < nums.size() - 1; i++) for(int j = i + 1; j < nums.size(); j++) if(nums[i] + nums[j] == target) { result.push_back(i); result.push_back(j); return result; } return result; } 

But in the last line, the return result doesn't seem to do anything, because when the numbers are found it is already return before it, but if I remove it, it will cause error. Does the last line slow my program down?

Answer 1

Question

Does the last line slow my program down?

This depends on what you intend to return when there are no pairs that sum to target. If you leave the last line out, your program would invoke undefined behavior when control flow reaches the end of the function body, and the compiler will rightfully warn you about that.

Integer overflow

There is an edge case that your code fails to handle — integer overflow. When the sum of nums[i] and nums[j] exceeds the range of int, undefined behavior is invoked.

Immediate improvements

Here are some improvements to your code:

• nums should taken by const reference, since it is not modified inside the function.

• A vector should be indexed with a std::size_t (or its size_type member type), because nums.size() might exceed the range of int.

• When nums is empty, nums.size() - 1 will produce SIZE_MAX, which is typically \$2^{32} - 1\$ or \$2^{64} - 1\$. This didn't cause a bug in this particular case, but it is definitely a logical mistake that should be fixed by, e.g., special-casing nums.size() < 2.

• You don't need to construct an empty result at the beginning — construct it on the fly by using return {nums[i], nums[j]} for example.

Here's the result: (overflow check is omitted for simplicity)

#include <cstddef> #include <vector> std::vector<std::size_t> find_numbers(const std::vector<int>& nums, int target) { if (nums.size() < 2) { return {}; } for (std::size_t i = 0; i < nums.size() - 1; ++i) { for (std::size_t j = i + 1; j < nums.size(); ++j) { if (nums[i] + nums[j] == target) { return {i, j}; } } } return {}; } 

Generalization

The function can be made more flexible by taking an iterator pair and a functor:

#include <iterator> #include <utility> // returns a pair of iterators [it_a, it_b] // such that it_a <= it_b && pred(*it_a, *it_b) // or [last, last] if such a pair is not found template <typename ForwardIterator, typename BinaryPredicate> auto find_pair( ForwardIterator first, ForwardIterator last, BinaryPredicate pred ) -> std::pair<ForwardIterator, ForwardIterator> { if (first == last) { return {last, last}; } for (auto next = std::next(first); next != last; ++first, ++next) { for (auto it = next; it != last; ++it) { if (pred(*first, *it)) { return {first, it}; } } } return {last, last}; } 

Optimization

The original algorithm runs in \$O(n^2)\$ time, which can be improved to \$O(n \log n)\$ for large inputs:

• First, maintain a vector of indexes sorted by the numbers.

• For each number, binary search for target - number.

Answer 2

Great answer by L. F.. With regards to optimization it can even be done in O(n) either by using a hash (assuming there aren't too many hash collisions):

std::vector<size_t> findNumbers( std::vector<int> const & nums, int const target ) { // pack numbers and indices into hash std::unordered_map<int,size_t> hash; hash.reserve( nums.size() ); for( size_t i=0; i<nums.size(); ++i ) { hash.emplace( nums[i], i ); } // for every number search for "target - number" for( size_t i=0; i<nums.size(); ++i ) { auto const el = hash.find( target - nums[i] ); if ( (el != hash.end()) && (i != el->second) ) { return { i, el->second }; } } return {}; } 

Or by using one of the non-comparison sorts.