Three algorithms for the two-sum problem.

two_sum.cpp

template<typename Iterator, typename Sum>
auto find_sum_pairs(Iterator begin, Iterator end, const Sum& target)
{
	std::vector<std::pair<Iterator, Iterator>> pairs;
	
	if (begin == end) return pairs;
	
	// O(N lg N)
	std::sort(begin, end--);
	
	// O(N)
	while (begin != end)
	{
		auto sum = *begin + *end;
		
		if (sum < target) ++begin;
		
		else if (sum > target) --end;
		
		else pairs.push_back({begin++, end});
	}
	
	// Time: O(N lg N + N) = O(N lg N)
	// Space: O(N)
	
	return pairs;
}

template<typename Iterator, typename T>
Iterator find_counterpart(Iterator begin, Iterator end, const T& value)
{
	if (begin == end) return end;
	
	auto middle = begin;
	
	std::advance(middle, std::distance(begin, end)/2);
	
	if (value < *middle)
	{
		auto result = find_counterpart(begin, middle, value);
		
		return result == middle ? end : result;
	}
	
	else if (value > *middle)
	{
		return find_counterpart(++middle, end, value);
	}
	
	else return middle;
}

namespace std
{
	template<typename Iterator>
	struct hash<std::pair<Iterator, Iterator>>
	{
		using result_type = long;
		using argument_type = std::pair<Iterator, Iterator>;
		
		result_type operator()(const argument_type& argument)
		{
			return *argument.first ^ *argument.second;
		}
	};
}

template<typename Iterator, typename Sum>
auto find_sum_pairs2(Iterator begin, Iterator end, const Sum& target)
{
	auto compare = [&] (const auto& first, const auto& second)
	{
		return ((first.first == second.first   &&
				first.second == second.second) ||
				(first.first == second.second  &&
				 first.second == second.first));
	};
	
	using pair_t = std::pair<Iterator, Iterator>;
	
	std::unordered_set<
					   	pair_t,
					   	std::hash<pair_t>,
					   	decltype(compare)
					  > pairs(4,
							  std::hash<pair_t>(),
							  compare);

	if (begin == end) return pairs;
	
	// O(N lg N)
	std::sort(begin, end);
	
	// O(N lg N)
	for (auto i = begin; i != end; ++i)
	{
		auto counterpart = find_counterpart(begin, end, target - *i);
		
		// 0 + 0 = 0 so need the second check
		if (counterpart != end && counterpart != begin)
		{
			pairs.insert({i, counterpart});
		}
	}
	
	// Time: O(2(N lg N)) = O(N lg N)
	// Space: O(N)
	
	return pairs;
}

template<typename Iterator, typename Sum>
auto find_sum_pairs3(Iterator original_begin, Iterator original_end, Sum target)
{
	// Assumes distinct items
	
	auto compare_values = [&] (const auto& first, const auto& second)
	{
		return ((first.first == second.first   &&
				 first.second == second.second) ||
				(first.first == second.second  &&
				 first.second == second.first));
	};
	
	using pair_t = std::pair<Iterator, Iterator>;
	
	std::unordered_set<
						pair_t,
						std::hash<pair_t>,
						decltype(compare_values)
					  > pairs(4,
							  std::hash<pair_t>(),
							  compare_values);
	
	if (original_begin == original_end) return pairs;
	
	using T = std::remove_reference_t<decltype(*original_begin)>;
	
	std::unordered_set<T> values(original_begin, original_end);
	
	// Time: O(N)
	for (auto i = values.begin(), end = values.end(); i != end; ++i)
	{
		auto counterpart = values.find(target - *i);
		
		// 0 + 0 = 0 so need the second check
		if (counterpart != end && counterpart != i)
		{
			Iterator first = original_end;
			Iterator second = original_end;
			
			for (auto begin = original_begin; begin != original_end; ++begin)
			{
				if (*begin == *i) first = begin;
				
				else if (*begin == *counterpart) second = begin;
				
				if (first != original_end && second != original_end) break;
			}
			
			if (first == original_end || second == original_end)
			{
				throw std::runtime_error("Something bad happened.");
			}
			
			pairs.insert({first, second});
		}
	}
	
	// Time: O(2N) = O(N)
	// Space: O(2N) = O(N)
	
	return pairs;
}