3
\$\begingroup\$

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?

\$\endgroup\$
0
6
\$\begingroup\$

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.

\$\endgroup\$
3
  • \$\begingroup\$ 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? \$\endgroup\$
    – user230763
    Sep 20 '20 at 4:52
  • \$\begingroup\$ @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. \$\endgroup\$
    – L. F.
    Sep 20 '20 at 4:53
  • \$\begingroup\$ Thank you for your help. \$\endgroup\$
    – user230763
    Sep 20 '20 at 5:27
3
\$\begingroup\$

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.

\$\endgroup\$
4
  • 2
    \$\begingroup\$ 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. \$\endgroup\$
    – slepic
    Sep 21 '20 at 7:35
  • 1
    \$\begingroup\$ Actually just skipping if i==el->second is enough to fix your implementation. I didnt realize the implications at first... \$\endgroup\$
    – slepic
    Sep 21 '20 at 9:33
  • \$\begingroup\$ Oh my. You're right. I've updated the answer. Thank you! \$\endgroup\$ Sep 22 '20 at 19:06
  • \$\begingroup\$ @slepic Or they could just build the hash during the search, inserting the current value only after checking for its partner. \$\endgroup\$ Sep 22 '20 at 20:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.