Wyznaczanie 4 liczb ciągu, które x+y+z=w

Mam problem z poniższym zadaniem:

Niech dany będzie zbiór liczb całkowitych nieujemnych S={a1,...,an}. Chcielibyśmy wiedzieć, ile jest takich
czwórek elementów x,y,z,w należących do S (niekoniecznie różnych), dla których zachodzi x+y+z=w.
Wejście
W pierwszym wierszu wejścia znajduje się jedna liczba całkowita n (1 n 5.000), oznaczająca wielkość
zbioru S. Drugi wiersz wejścia zawiera n liczb całkowitych a1,...,an (0 ai 500.000), pooddzielanych
pojedynczymi odstępami i definiujących zbiór S. Liczby te są parami różne.
Wyjście
Pierwszy i jedyny wiersz wyjścia powinien zawierać jedną liczbę całkowitą, oznaczającą liczbę sposobów
wyboru czterech liczb x,y,z,w ze zbioru S, dla których x+y+z=w.
Przykład
Dla danych wejściowych:
4
1 2 3 4
poprawnym wynikiem jest:
4
Wszystkimi szukanymi czwórkami są w tym przypadku: (1,1,1,3), (1,1,2,4), (1,2,1,4) oraz (2,1,1,4). Przy okazji przypominamy,
że elementy w czwórce mogą się powtarzać

Bardzo proszę o podpowiedzi lub cokolwiek co mogłoby mi pomóc w rozwiązaniu tego zadania.

4 zagnieżdżone fory i ręcznie sprawdzanie? Długo zejdzie ale tutaj chyba innego sposobu nie ma.

edit: starczy 3 pętle, i sprawdzenie czy wynik dodawania znajduje się wśród wprowadzonych liczb. Dalej marnie z czasem ale lepiej niż 4 pętle, o ile posortujemy tablicę wejściową. Warto też usunąc powtarzające się liczby z wejścia, skoro w obliczeniach mogą się powtarzać to nie ma znaczenia czy będzie tam 10 razy 5 czy jedna. A zawsze zmniejszymy tablicę a w raz z nią czas obliczeń.

Ja bym popróbował algorytmu dynamicznego podobnego do algorytmu wydawania reszty.

Hm a jak by tak 3 zagnieżdżone pętle i sprawdzanie sumy w drzewie binarnym?

4 zagnieżdżone fory i ręcznie sprawdzanie? Długo zejdzie ale tutaj chyba innego sposobu nie ma.

Jasne, a jedyny sposób na sortowanie to generowanie wszystkich permutacji ciągu i sprawdzanie która jest poprawna ;].

Popatrz na to tak:
x+y+z=w

Czyli:
x+y=w-z

Czyli po lewej stronie masz n^2 różnych par liczb, tak samo po prawej stronie - n^2 różnych różnic (hmm).
Wystarczy sprawdzić dla każdej pary z lewej strony czy istnieje jakaś para z prawej strony o równej wartości - np. za pomocą hashmapy, w czasie O(1).

sumy = { zbiór par (a, b) } # implementacja - np. lista, albo lepiej, generowanie na bieżąco
różnice = { zbiór par (a, b) } # implementacja - hashmapa.

for suma in sumy:
    if różnice.contains(suma) or różnice.contains(-suma): # `or`, bo kolejność w różnicy ma znaczenie
        znaleziono rozwiązanie

Złożoność - O(n^2).

Musi działać, chyba że o czymś nie pomyślałem.

edit:
Zasadniczo inspiracji szukaj tutaj: http://en.wikipedia.org/wiki/3SUM.

W sumie to na samym początku można by wyeliminować z dalszych obliczeń (niezależnie od metody) wartość maksymalną, albo są zera i wtedy do wyniku dodajemy liczbę 1, albo też nie ma i wtedy dodawanie z nią nijak nie może dać sumy znajdującej się w ciągu.

edit: niezależnie od metody warto zmniejszyć N jeszcze bardziej, eliminując powtórzenia się liczb w tablicy wejściowej, tak czy siak możemy używać ich wielokrotnie.

Całość da się napisać w czasie liniowym o ile już są posortowane, jak nie - to standardowe z sortowania n*log(n)
EDIT: a może i nie, opiszę algorytm a potem może ktoś da rady powiedzieć coś o jego złożoności.

1. Sortujemy rosnąco
2. Ustawiamy x,y,z,w jako indeksy na początek tablicy
3. zwiększamy indeks 'w' dopóki T[x]+T[y]+T[z]>T[w] jeżeli koniec tabeli to koniec algorytmu
4. jeżeli T[x]+T[y]+T[z]=T[w] to mamy kolejną czwórkę
5. znajdujemy mniejsze z T[x+1]-T[x],T[y+1]-T[y],T[z+1]-T[z] i zwiększamy odpowiednio x,y lub z (tu trzeba wprowadzić zabezpieczenie aby nie wyleźć poza)
6. jeżeli coś udało się zwiększyć w poprzednim kroku to przechodzimy do pkt 3, jak nie udało się to koniec algorytmu

Chyba przekombinowałem ...

@up
W jednym z punktów opisałeś, że znajdujemy min z T[x+1]-T[x] , T[y+1]-T[y] , T[z+1]-T[z] .
Rozważmy przykład liczb 1 , 2 , 3 , 4
Mamy ustawione w , y , z i x na indeksie pierwszym czyli 1
zwiększamy w dopóki z+x+y > w
W takim wypadku w wędruje na indeks 3 czyli do trójki.
1+1+1=3 okej ;) mamy 1 Czwórkę
Co teraz należy wykonać jeżeli wszystkie różnice następnego i poprzedniego indeksu dla x,y i z są takie same ?
Jak sprawdzić kolejne możliwości czwórek jeżeli będą to 1+2+1=4 , 2+1+1=4 oraz 1+1+2 = 4 ??

Jak dla mnie 1+1+2 = 1+2+1 = 2+1+1 to te same trójki.
Jeżeli dla ciebie to są różne trójki to liczymy Q=(a!=b)+(b!=c)+(c!=a) oraz zwiększamy licznik trójek o Q! (prościej zorganizować przez tabelkę Add[]={1,666,2,6};)

Lub rozwiązać zadanie inną metodą - poprzez programowanie dynamiczne.
Dal każdej liczby w przedziale 0..max(T) pamiętamy liczbę możliwych jedynek, dwójek, trójek.