Chcę rozwiązaćto Wyzwanie CodeChef:

Załóżmy, że otrzymaliśmy tablicę A elementów N (o zasięgu 100 000). Mamy znaleźć liczbę wszystkich par 3 takich elementów 1 <= Ai, Aj, Ak <= 30 000 takich, że

Aj-Ai = Ak- Aj and i < j < k

Innymi słowy Ai, Aj, Ak są w progresji arytmetycznej. Na przykład dla Array:

9 4 2 3 6 10 3 3 10

więc AP to:

{2,6,10},{9,6,3},{9,6,3},{3,3,3},{2,6,10} 

Wymagana odpowiedź to 5.

Moje podejście

Próbowałem pobrać 30 000 długich tablic o nazwie przeszłej i prawej. Początkowo prawo zawiera liczbę każdego elementu 1-30 000.

Jeśli jesteśmy na i-tej pozycji, przechowujemy liczbę wartości tablicy, zanim i i prawo zapisze liczbę tablic po i. Po prostu pętlę dla wszystkich możliwych wspólnych różnic w tablicy. Oto kod:

right[arr[1]]--;

for(i=2;i<=n-1;i++)
{
    past[arr[i-1]]++;
    right[arr[i]]--;
    k=30000 - arr[i];
    if(arr[i] <= 15000)
        k=arr[i];
    for(d=1;d<=k;d++)
    {
        ans+= right[arr[i] + d]*past[arr[i]-d] + past[arr[i] + d]*right[arr[i]-d];
    }
    ans+=past[arr[i]]*right[arr[i]];
}

Ale to powoduje przekroczenie limitu czasu. Pomóż z lepszym algorytmem.