Tablica liczb i trójki z nich sumujące się do zera

Mam takie zadanie:

Zadaniem programu jest wczytanie liczb całkowitych, a następnie znalezienie wśród nich trójek liczb sumujących się do zera, liczby są niepowtarzalne, dopuszczamy tylko jedną ich kombinację.

Bardzo prostym przykładem może być:

a: -1
b -3
c: 4
d: 3
e: -2
f: 1

daje odpowiedź 2, bo:

b + a + c = 0
e + a + d = 0

Charakterystyka wejścia:

t – liczba testów (do 5)
n – ilość liczb (do 10000)

… - kolejne liczby

Wyjście:

k – liczba trójek sumujących się do zera (do 1000)
a b c – trójki liczb (oddzielone spacjami) sumujące się do zera w rosnącej kolejności (kolejność rosnąca trójek i kolejność rosnąca w trójkach)
Uwaga: żeby nie przepełnić strumienia wejścia trójki liczb wyświetlamy jedynie dla k < 100, w innym wypadku wyświetlamy samo k.

np.:

Wejście:

1
10
-4
3
-2
1
6
7
-1
-5
-3
2

Wyjście:

8
-5 -2 7
-5 -1 6
-5 2 3
-4 -3 7
-4 -2 6
-4 1 3
-3 1 2
-2 -1 3

Napisałem algorytm ale jest za wolny, bo jest to niemalże brute-force, więc nic dziwnego. W jaki sposób można to zrobić szybciej? Szukam algorytmów z tym związanych ale nie mogę nic znaleźć.

Dzięki za wszelką pomoc.

Jakie są wymogi czasowe? Rozwiązanie kwadratowe jest bardzo proste, ale n = 10^4 przy O(n^2) jest na granicy tego, co można uznać za policzalne w sensownym czasie.

Niestety nie znam wymogów czasowych...ma być jak najszybciej się uda.

Chociaż teraz zrobiłem z kwadratową złożonością i zacząłem dostawać błędną odpowiedź, więc chyba jest wystarczająco. Tylko nie wiem w czym tkwi błąd, wyjście mam takie samo jak w danych przykładowych.

Krok 1 sortowanie o(n log n)
Krok 2 po przesortowaniu trzeba mądrze napisać algorytm przeszukiwania kombinacji (tak by szukał liczb tylko w porządku rosnącym).
Przy czym należy zauważyć, że suma dwóch najmniejszych liczb wyznacza największą liczbę jaką można użyć (i na odwrót suma dwóch największych ...). być może wyciśniesz jeszcze inne ograniczenia. Tu prawdopodobnie też się wyciśnie o(n log n)

Edit: PS: niestety jest to jedno z zadań, gdzie sposób wczytywania danych też jest ważny (masz dużo danych wejściowych). Pokaż jak to zrobiłeś to naprowadzimy cię jak szybciej wczytywać te dane. Dane wyjściowe są spoko bo jest ograniczenie na liczbę trójek, które należy podawać, więc nie ma co tu optymalizować.

A czy nie ma przypadkiem jakichś ograniczeń co do samych liczb?

pesymistyczna złożoność obliczeniowa n², w praktyce dla danych zdefiniowanych w pierwszej linijce wyrabia się w jednym wątku na moim i7 2670 w półtorej sekundy z 12.5M wyników. algorytm jest bardzo łatwy do implementacji wielowątkowej, wtedy działa szybciej proporcjonalnie do ilości wątków.

			// jakieśtam dane - 10000 liczb w miarę symetrycznie rozłożonych względem zera
			var c = new int[10000]; for (int i = 0; i < c.Length; i++) c[i] = -i + c.Length/2;
			//var c = new int[] { -4, 3, -2, 1, 6, 7, -1, -5, -3, 2 };

			Array.Sort(c); // c posortowane
			int max = c[c.Length - 1], count = 0;

			// pętla po wszystkich liczbach poza dwiema ostatnimi - przedostatnia zarezerwowana na b, ostatnia na sumę
			for (int i = 0; i < c.Length - 2; i++) 
			{
				int a = c[i];
				for (int j = i + 1; j < c.Length - 1; j++) // pętla dla liczb większych od a
				{
					int b = c[j], res = a + b;

					// to dość istotne optymalizacje, ale już wyleciały mi głowy uzasadnienia ich użycia
					if (res >= 0 || res >= -b || res >= -a) break;

					// jeśli -suma (czyli trzecia liczba) większa od największej dostępnej w tablicy, to nie ma co jej tam szukać
					if (-res > max)
						continue;

					// o dziwo w c# BinarySearch nawet dla tablicy 10k elementów jest kilkakrotnie szybszy od HashMap
					if (Array.BinarySearch(c, -res) > 0)
					{
						count++;
						//Console.WriteLine("{0} {1} {2}", a, b, -res);
					}
				}
			}

			Console.WriteLine("{0}, {1:F4}ms", count, 1000f * (float)sw.ElapsedTicks / System.Diagnostics.Stopwatch.Frequency);

[edit]
ha ha, dla symetrycznej tablicy 100k liczb dostałem w 163s 1,249,975,000 wyników ;] jak by nie patrzeć kwadratowa złożoność obliczeniowa.

Juz wszystko ok, dzieki za odpowiedzi ;) Dla paru testow zle sie pokazywalo, ale posortowalem na wszelki wypadek jeszcze wyjscie, wyswietlilem i przeszlo juz bez problemu. Potem napisalem kod od nowa i juz normalnie przeszlo, bez sortowania wyjscia. Gdzies musialem sie walnac wczesniej.

@ŁF, mam chyba lepszy pomysł, z tym że nie mogę określić złożoności, wygląda mi na O(N*log(N)):

typedef int CMP(const void *a,const void *b);
int cmp(const int *a,const int *b) { return (*a>*b)-(*a<*b); }

int main()
  {
   unsigned TestCount;
   scanf("%u",&TestCount);
   while(TestCount--)
     {
      unsigned ValueCount;
      scanf("%u",&ValueCount);
      static int V[1000];
      for(unsigned i=0;i<ValueCount;++i) scanf("%d",V+i);
      qsort(V,ValueCount,sizeof(int),(CMP*)cmp);
      static struct { int a,b,c; } R[100];
      unsigned ResultCount=0;
      int *a=V,*e=V+ValueCount;
      while(a+1<e)
        {
         bool found=false;
         int *p=a,*q=e,v=-(*(p++)+*(p++));
         while(p<q)
           {
            int *m=p+((q-p)>>1);
            if(*m>v) q=m;
            else if(*m<v) p=m+1;
            else q=p=m+1;
           }
         int *bs=a+1,*c=p-1;
         while(bs<c)
           {
            p=bs;
            q=c+1;
            v=-(*a+*c);
            while(p<q)
              {
               int *b=p+((q-p)>>1);
               if(*b>v) q=b;
               else if(*b<v) p=b+1;
               else
                 {
                  if(ResultCount<100)
                    {
                     R[ResultCount].a=*a;
                     R[ResultCount].b=*b;
                     R[ResultCount].c=*c;
                    }
                  ++ResultCount;
                  p=q=b+1;
                 }
              }
            bs=p;
            --c;
           }
         ++a;
        }
      printf("%d\n",ResultCount);
      if(ResultCount<=100)
        {
         for(unsigned r=0;r<ResultCount;++r) printf("%d %d %d\n",R[r].a,R[r].b,R[r].c);
        }         
     }
   return 0;
  }