Finding indices of numbers that sum to a target

I've taken this algorithm question, which is to find the indexes of any two numbers in an array that sum to a given number. It is quite a simple problem to solve. But it is the execution time of my code algorithm that bugs me.

#include 
#include 
using namespace std;

class TwoSum
{
public:
  static std::pair findTwoSum(const std::vector& list, int TargetSum)
  {
    for (int increment = 0; increment  list = {1, 3, 5, 7, 9 };
   int targetSum = 12;
   pair indices = TwoSum::findTwoSum(list, targetSum);

   indices.first == -1 && indices.second == -1 ?
   cout << "No vector elements can be added to achieve the target sum" << endl :
   cout << "The target sum can be achieved by adding the vector element " << indices.first << " and " << indices.second;
   cout << endl;

   return 0;
}

It is guaranteed correct as I tested it with the website's compiler (or whatever you call it), they can test your code just by pasting and running it on their code editor. I tested this on my IDE as well, and it worked fine.

The problem is, my code failed the performance test when dealing with large number of vector elements as it took longer than the website's expectation. For me, the function named findTwoSum()is already straightforward. And I don't have any idea how to optimize this function. Note that the test's focus here is the function itself and how fast it executes.

Any modifications in function's return type and parameter is not allowed. As the website stated that you cannot modify the main function's contents, implying that you cannot also change how the function is called.

But I slightly modified the main function for you to know what the program is trying to achieve.

Not quite right

First off, you're checking every cross pair of indices against each other. But that means that findTwoSum({1, 3, 4}, 6) will succeed, even though there is no pair of elements that sum to 6 - because you count the 3 twice. You need: "any two distinct elements".

Iterating over vectors

list is a confusing name for a vector. increment is a poor variable name for this - since it's not incrementing anything, it's just another index, so you really should use i and j instead. Also you don't need at() - that member function does range checking. But your indices will all definitely be in range, so you could simply write:

for (size_t i = 0; i < v.size(); ++i) {
    for (size_t j = i+1; j < v.size(); ++j) { // correcting initial bug
        if (v[i] + v[j] == target) {
            return std::make_pair(i, j);
        }
    }
}
return std::make_pair(-1, -1);

Failure case

Rather than using sentinel values, I prefer to use something like Boost.Optional to indicate failure, so that:

boost::optional> findTwoSum(const std::vector&, int target);

Classes

Why is findTwoSum a static member function? Just make it a free function. There's no reason for a class. You could instead make TwoSum a namespace but I don't see the point of that either.

The Algorithm

You are checking every pair of indices - that's \$O(n^2)\$. We can do way better. Consider that once we have our first index - there is one unique element that we need to find to see if we have a success case: target - v[i].

We could simply throw all of our indices into a map:

std::unordered_map indices;
for (size_t i = 0; i < v.size(); ++i) {
    indices.insert(std::make_pair(v[i], i));
}

And then simply search if target - v[i] is in indices for each such i:

for (size_t i = 0; i second);
    }
}

This will be \$O(n)\$ to create the hashtable, and then another \$O(n)\$ to do all the searching... for a grand total of \$O(n)\$.

StackExchange Code Review Q#114159, answer score: 11