Algorytmiczna łamigłówka - napisanie funkcji o złożoności O(n*n)

Cześć, mam taki problem, że chciałbym napisać funkcję która ma następującą specyfikację:
Wejście:
n,s - dodatnie liczy naturalne
a - tablica jednowymiarowa z liczbami z zakresu od 1 do n*n

Wyjście:
1 gdy da się otrzymać liczbę s z trzech elementów ze zbioru a[0],a[1]...a[n-1]
0 w przeciwnym wypadku

Łatwo zrobić to w złożoności O(nnn), ale jak napisać to w złożoności nie przekraczającej O(n*n)?

Co to

da się otrzymać liczbę s z trzech elementów
znaczy?

Ale ile jest tych liczb? n czy n²? Bo napisałeś że zbiór a[0],...,a[n-1] co by sugerowało że liczb jest n ale piszesz też o zakresie od 1 do n², więc jak to jest? Jeśli liczb jest n to zadanie jest trywialne i to zrobienia średnio w O(nlogn) a pesymistycznie w O(n²) - sortujesz dane w O(nlogn) a potem po kolei bierzesz sobie każdą liczbę (O(n)) i dla niej szukasz połowkowo (s-a[i])/2 czyli połowy liczby potrzebnej do sumy (O(logn)) i potem lecisz z tego miejsca w dwie strony (bierzesz jedną liczbę z jednej strony, drugą z drugiej, jeśli suma jest za duża to cofasz lewy wskaźnik a jak za mała to przesuwasz dalej prawy wskaźnik) szukając takiej pary liczb która sie zsumuje do potrzebnej wartości. Pesymistytcznie dopiero pierwsza i ostatnia liczba dadzą odpowiednią sumę więc poszukiwanie będzie kosztować O(logn)+O(n) = O(n).

1. posortować jeśli nie jest posortowane o(n log n)
2. wyszukiwać parę o(n^2) i na podstawie tych dwóch policzyć ile ma wynosić ten trzeci i następnie wyszukać go binarnie. W sumie (razem z sortowaniem) da to złożoność o(n^2 log n).

Bez brakujących konkretów nie da się z tego wycisnąć dużo więcej. No można jeszcze stworzyć hash table zredukować wyszukiwanie brakującego elementu do stałego czasu i w efekcie można osiągnąć to o(n^2)

Jeśli chodzi o ten zakres, to miałem tu na myśli zakres liczb w ciągu. Albo inaczej: wielkość liczb :D nie wiem jak to inaczej napisać