TwoSum.cpp

#include <stdlib.h>
#include <stdio.h>
#include <random>
#include <vector>
#include <unordered_map>
#include <algorithm>
#include <optional>
#include <intrin.h>
#include <inttypes.h>

constexpr size_t count = 10000;
constexpr int minimum = -1000000000;
constexpr int maximum = +1000000000;

std::vector<int> generateInput( int target )
{
	// Deliberately seeding RNG with 0, to generate same output every time
	std::mt19937 gen( 0 );
	std::uniform_int_distribution<int> distrib( minimum, maximum + 1 );
	std::vector<int> res;
	res.resize( count );
	for( int& i : res )
		i = distrib( gen );

	// Make the correct output to be [ 0, count - 1 ]
	res[ count - 1 ] = target - res[ 0 ];
	return res;
}

std::optional<std::pair<uint16_t, uint16_t>> solveWithHash( const std::vector<int>& vec, int target )
{
	// Ported from there: https://nullprogram.com/blog/2023/06/26/
	std::unordered_map<int, uint16_t> map;
	for( size_t i = 0; i < vec.size(); i++ )
	{
		const int num = vec[ i ];
		const uint16_t idx = (uint16_t)i;
		const int complement = target - num;
		auto it = map.find( complement );
		if( it != map.end() )
			return std::make_pair( it->second, idx );
		map.insert( std::make_pair( num, idx ) );
	}

	return {};
}

std::optional<std::pair<uint16_t, uint16_t>> solveWithSort( const std::vector<int>& vec, int target )
{
	// Copy integers into another vector, with values and indices
	struct alignas( 8 ) Entry
	{
		int num;
		uint16_t idx;
		bool operator <( const Entry& e ) const
		{
			return num < e.num;
		}
	};

	std::vector<Entry> temp;
	// The next line is probably the only malloc() in this implementation
	temp.resize( vec.size() );
	for( size_t i = 0; i < vec.size(); i++ )
	{
		temp[ i ].num = vec[ i ];
		temp[ i ].idx = (uint16_t)i;
	}

	// Sort the temporary vector
	std::sort( temp.begin(), temp.end() );

	// Find the solution
	using It = std::vector<Entry>::const_iterator;
	It rangeBegin = temp.begin();
	It rangeEnd = temp.end() - 1;
	while( rangeBegin < rangeEnd )
	{
		const int s = rangeBegin->num + rangeEnd->num;
		if( s > target )
			rangeEnd--;
		else if( s < target )
			rangeBegin++;
		else
			return std::make_pair( rangeBegin->idx, rangeEnd->idx );
	}
	return {};
}

int main()
{
	// Flip this boolean to switch between the two implementations
	constexpr bool useHashMap = false;

	const int sum = 11;
	const std::vector<int> vec = generateInput( sum );
	const int64_t tscStart = __rdtsc();
	const auto res = useHashMap ? solveWithHash( vec, sum ) : solveWithSort( vec, sum );
	const int64_t elapsed = __rdtsc() - tscStart;

	if( res )
		printf( "[ %i, %i ]", (int)res->first, (int)res->second );
	else
		printf( "Not found" );
	printf( "; elapsed time: %" PRIu64 "\n", elapsed );
	return 0;
}