Normally, we'd use the vector's index type (std::vector<int>::size_type
, i.e. std::size_t
) for the return values. But unfortunately we're required to return negative values when the search fails, so I'd recommend a pair of std::ptrdiff_t
instead. And the question specifically asks for int
s, so I'd just insert a comment explaining that were limited to arrays of up to INT_MAX
elements (the O(n²) scaling probably reduces the practical range, anyway).
I don't see anywhere that says there can't be negative numbers present - if that's specified, then it would have been wise to quote that part. As it is, you've introduced a bug - because we're not storing numbers larger than sum
into com
, the index calculation it - com.begin() + 1
will be incorrect by the amount of omitted large numbers (also, where does the +1
come from? - did you misread zero-based indices in the question?).
The vector com
could grow to (in the worst case) the same size as the input vector. That's quite a lot of extra storage. It might be more efficient to leave the >= sum
elements in place, and just search the beginning half of the input vector (no extra storage needed).
That looks like the following (making a few other simplifications, such as using an iterator instead of count
, and reducing the scope of the find
result):
static std::pair<int, int> findTwoSum(const std::vector<int>& list, int sum)
{
for (auto it_b = list.begin(); it_b != list.end(); ++it_b) {
if (auto it_a = std::find(list.begin(), it_b, sum - *it_b); it_a != it_b) {
return {it_a - list.begin(), it_b - list.begin()};
}
}
return {-1, -1};
}
We still have a pretty inefficient algorithm - it's O(n²), where n is the length of list
, because for every element in list
, we perform a linear search for its complement. We can reduce that, at the cost of reintroducing extra storage, by maintaining a set of seen values. That may seem little different to the present approach of maintaining a vector, but the advantage is that search scales much better with size. What we actually need is a map, as we'll want to note the corresponding index to return as result; the best choice is std::unordered_map
:
Unordered map is an associative container that contains key-value pairs with unique keys. Search, insertion, and removal of elements have average constant-time complexity.
That gives us:
std::unordered_map<int, int> seen; // value -> index
for (auto it_b = list.begin(); it_b != list.end(); ++it_b) {
if (auto it_a = seen.find(sum - *it_b); it_a != seen.end()) {
return {it_a->second, it_b - list.begin()};
} else {
seen[*it_b] = it_b - list.begin();
}
}
Modified code
#include <unordered_map>
#include <utility>
#include <vector>
static std::pair<int, int> findTwoSum(const std::vector<int>& list, int sum)
{
std::unordered_map<int, int> seen; // value -> index
for (auto it_b = list.begin(); it_b != list.end(); ++it_b) {
if (auto it_a = seen.find(sum - *it_b); it_a != seen.end()) {
return {it_a->second, it_b - list.begin()};
} else {
seen[*it_b] = it_b - list.begin();
}
}
return {-1, -1};
}
And a very simple test program:
#include <iostream>
int main()
{
auto const [a, b] = findTwoSum({ 1, 3, 5, 7, 9 }, 12);
std::cout << a << ',' << b << '\n';
}
O(n^2)
\$\endgroup\$O(n^2)
. In worst case you will be traversing wholelist
, which gives youO(n)
for the traversal itself. In addition, in each iteration you do a linear search (std::find
) which gives youO(n^2)
in total. \$\endgroup\$O(n * lg n)
. Marching from the left and right to find a sum is likelyO(n)
. \$\endgroup\$