Podejście teoretyczne i idealistyczne
Wrzucasz wszystkie liczby do hash mapy. n liczb, wrzucenie do hash mapy 1 elementu O(1). Całość O(n)
Dla każdej liczby a wyliczenie b = sum - a i sprawdzenie, czy b jest w hash map. n liczb do sprawdzenie, idealnie sprawdzenie czy b jest w hashmapie O(1). Całość O(n)
Ponieważ O(n) + O(n) = O(n) to całość zadania ma O(n)
W praktyce, jakby to na konkretnym zestawie danych benchmarkować, to hash map załadowana np. w 50% nie ma pobrania O(1) bo w jednym bucket będzie więcej jak jedno trafienie po wyliczeniu hash dla klucza i modulo dla rozmiaru bucketów.
Konflikt może być rozwiązany linked list, można iść w red black tree, albo mądrzy ludzie 'theoretical computer science' u Smoka wiedzą jak (ja jestem za cienki)
Po treści wnioskuję, że w zadaniu chodzi o pokazanie, że O(n) i na tym koniec.
*W praktyce zależy od implementacji.
Np. weżmy nie C/C++ ale JavaScript. Dwie klamry {} to już hashmap. Konia z rzędem i wóz szacunku dla tego kto będzie wgłębiony w implementację tego w ES5, ES6, ES2018.
W Java też, większość materiałów uczy o LinkedList w HashMap a jak pamiętam, od którejś wersji implementacja została zmieniona na self-balancing tree