Given a vector and a target sum, returns zero-based indices of any two distinct elements whose sum is equal to the target sum I am trying to solve 4. Two Sum from this set of C++ interview questions. As far as I can think this solution has a time complexity of \$O(n \log n)\$ can it be further optimized?


  Write a function that, given a vector and a target sum, returns
  zero-based indices of any two distinct elements whose sum is equal to
  the target sum. If there are no such elements, the function should
  return (-1, -1).
  
  For example, findTwoSum({ 1, 3, 5, 7, 9 }, 12) should return a
  std::pair&lt;int, int&gt; containing any of the following pairs of indices:
  
  
  1 and 4 (3 + 9 = 12) 
  2 and 3 (5 + 7 = 12) 
  3 and 2 (7 + 5 = 12) 
  4 and 1 (9 + 3 = 12)
  


Here is my approach  considering that negative numbers cannot be present in vector

static std::pair&lt;int, int&gt; findTwoSum(const std::vector&lt;int&gt;&amp; list, int sum)
{
    std::vector&lt;int&gt; com;
    std::vector&lt;int&gt;::iterator it;
    for(unsigned count=0; count&lt;list.size(); count++){
        it = std::find(com.begin(), com.end(), list[count]);
        if ( it != com.end() ){
            return std::make_pair(it - com.begin() + 1, --count);
        }
        else{
            if(sum &gt;= list[count])
            com.push_back(sum-list[count]);
        }

    }
    return std::make_pair(-1,-1);
}
Normally, we'd use the vector's index type (std::vector&lt;int&gt;::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 ints, 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 &gt;= 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&lt;int, int&gt; findTwoSum(const std::vector&lt;int&gt;&amp; 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&lt;int, int&gt; seen; // value -&gt; 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-&gt;second, it_b - list.begin()};
        } else {
            seen[*it_b] = it_b - list.begin();
        }
    }




Modified code

#include &lt;unordered_map&gt;
#include &lt;utility&gt;
#include &lt;vector&gt;

static std::pair&lt;int, int&gt; findTwoSum(const std::vector&lt;int&gt;&amp; list, int sum)
{
    std::unordered_map&lt;int, int&gt; seen; // value -&gt; 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-&gt;second, it_b - list.begin()};
        } else {
            seen[*it_b] = it_b - list.begin();
        }
    }
    return {-1, -1};
}


And a very simple test program:

#include &lt;iostream&gt;
int main()
{
    auto const [a, b] = findTwoSum({ 1, 3, 5, 7, 9 }, 12);
    std::cout &lt;&lt; a &lt;&lt; ',' &lt;&lt; b &lt;&lt; '\n';
}