Учитывая набор целых чисел, задача состоит в том, чтобы найти количество возможных арифметических рядов длины 3. Набор целых чисел может или не может быть отсортирован.

Я мог бы реализовать простой алгоритм грубой силы, требующий времени O (n ^ 3), но эффективность времени важна, и набор целых чисел может достигать 10 ^ 5. Это означает, что брутфорс явно выигралт работа. Кто-нибудь может предложить какой-нибудь алгоритм / псевдокод / код в C ++?

Пример: есть 4 числа 5,2,7,8. Очевидно, что существует только одна такая возможность - (2,5,8), в которой общая разница равна 3, поэтому наш ответ равен 1.

РЕДАКТИРОВАТЬ: Я забыл упомянуть одно важное свойство - каждое число заданных наборов составляет от 1 до 30000 (включительно).