Ich will lösendiese CodeChef Herausforderung:

Angenommen, wir erhalten ein Array A mit N (im Bereich von 100.000) Elementen. Wir sollen die Anzahl aller Paare von 3 solchen Elementen 1 <= Ai, Aj, Ak <= 30.000 so finden, dass

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

Mit anderen Worten, Ai, Aj, Ak befinden sich in der arithmetischen Progression. Zum Beispiel für Array:

9 4 2 3 6 10 3 3 10

Also die AP sind:

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

Die erforderliche Antwort lautet also 5.

Mein Ansatz

Was ich ausprobiert habe, ist, 30.000 lange Arrays zu nehmen, die früher und später als richtig bezeichnet wurden. Anfänglich enthält rechts die Anzahl jedes 1-30.000 Elements.

Wenn wir uns an der letzten Position befinden, werden die Werte des Arrays vor i und rechts die Werte des Arrays nach i gespeichert. Ich schleife einfach nach allen möglichen gemeinsamen Unterschieden im Array. Hier ist der Code:

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]];
}

Aber das bringt mir Zeitlimit überschritten. Bitte helfen Sie mit einem besseren Algorithmus.