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.

• user230763: I don't know the function can use return{} instead of returning a vector, so from now on I should use return {} for every functions?
• L. F.: @user230763 return {}; is basically a shorthand for return std::vector{}; in this case. Of course you shouldn't use it for every function - use it if you want to return a default-constructed value.
• user230763: Thank you for your help.

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.

• slepic: If i give you array {2,3,4} and target sum 4, your implementation returns {0,0}, which is incorrect. The second loop should only return if i != el->second unless you can find the same element in nums again before el->second. Which means that you would be back to O(n^2) again unless you change the hash to something that can keep track of up to 2 indices per element.
• slepic: Actually just skipping if i==el->second is enough to fix your implementation. I didnt realize the implications at first...
• Dino Malpera: Oh my. You're right. I've updated the answer. Thank you!
• superb rain: @slepic Or they could just build the hash during the search, inserting the current value only after checking for its partner.