Я хочу решитьэтот Задача CodeChef:

Предположим, нам дан массив A из N (в диапазоне 100 000) элементов. Мы должны найти количество всех пар 3 таких элементов 1 <= Ai, Aj, Ak <= 30000 таких, что



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



Другими словами, Ai, Aj, Ak находятся в арифметической прогрессии. Например, для массива:

9 4 2 3 6 10 3 3 10

Итак, AP:

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

Таким образом, обязательный ответ 5.

Мой подход

Я попробовал взять 30 000 длинных массивов, названных прошлым и правильным. Первоначально право содержит количество каждого 1-30 000 элементов.



Если мы находимся в i-ой позиции, то прошлое сохраняет количество значений массива до i, а справа - число массивов после i. Я просто зацикливаюсь на все возможные общие различия в массиве. Вот код:

right[arr[1]]--;

for(i=2;i