Найти арифметическую прогрессию в массиве? Есть массив на 10**5 элементов , содержащие элементы из [0; 10**18] . Гарантируется , что найдутся 10**4 чисел, которые образуют арифметическую прогрессию . Вопрос , как найти эту самую прогрессию?

Предыдущий
вопрос Следующий
вопрос

Для поиска арифметической прогрессии в массиве можно воспользоваться следующим методом:

Отсортировать массив по возрастанию.Пройтись по всем возможным парам элементов массива (i, j) и для каждой пары проверить, образуют ли они с неким третьим элементом также прогрессию. То есть, проверить, есть ли в массиве элемент i + (i - j), где i, j - индексы элементов массива.Если прогрессия найдена, то вывести эти три числа.Если прогрессия не найдена, увеличить j на 1 и вернуться к шагу 2.

Этот метод имеет временную сложность O(n^2), что может быть эффективно при таком большом массиве.