main.cpp

#include <iostream>
#include <vector>
#include <unordered_map>

//using namespace std;

std::vector<int> find_sum(const std::vector<int> &list, int target_sum) // O(n)
{
	std::unordered_map<int, int> all_compl;

	for(auto i : list) // O(n)
	{
		auto it = all_compl.find(i); // find - O(1)

		if (it != all_compl.end())
			return {it->first, it->second};

		int complementary = target_sum - i;

		all_compl[complementary] = i; // append - O(1)
	}

	return {};
}

int main()
{
	std::vector<int> list = {1,2,3,4,5,6};
	int target_sum = 10;
	
	std::vector<int> answer = find_sum(list, target_sum); // O(n)


	std::cout << "{";
	for (auto i: answer)
		std::cout << i << " ";
	std::cout << "}" << std::endl;

	return 0;
}

Main.hs

module Main where

import qualified Data.Map as M
-- :set -package containers

list1 = [1,2,3,4,5,6]
targetSum1 = 10

myFind :: (Ord a, Num a) => [a] -> a -> [a]
myFind list targetSum = myFind' Nothing list M.empty targetSum

-- myFind' is O(n * log n)
myFind' (Just a) _      _       tsum = [a, tsum-a]
myFind' _        []     _       tsum = []
myFind' Nothing  (x:xs) someMap tsum = myFind' element xs newSomeMap tsum
  where
    newSomeMap = (M.insert (tsum - x) x someMap) -- O(log n)
    element = (M.lookup x someMap)               -- O(log n) 😥
    
-- А нужно было использовать пакет hashtables (а именно BasicHashTable) !
    
main :: IO ()
main = do
  putStrLn $ show $ myFind list1 targetSum1