How to find an arithmetic progression in a list?

Question

Python

Suppose there is a list [1487, 1847, 4817, 4871, 7481, 7841, 8147, 8741] and this list contains an arithmetic progression 1487, 4817, 8147 with a step of 3330. What is the optimal algorithm for finding such an arithmetic progression? The list may be random.

Answer 1

Wrote this solution. Clarification: in my case, it is known in advance that we are looking for triples

lst=[1487, 1847, 4817, 4871, 7481, 7841, 8147, 8741]
    for i in range(len(lst)):
        for j in range(i+1,len(lst)):
            diff=lst[j]-lst[i]
            if lst[j]+diff in lst:
                print(lst[i],lst[j],lst[j]+diff)

Answer 2

Is the interval known in advance? If not, how many numbers would be considered a progression? more than 2?
Take unique values, sort in ascending order, push into hash and then search, starting with the smallest, look at the difference with each larger number and check for the presence of a larger number * 2 minus a smaller number.
For example, for the sequence 8, 4, 12, 7, 3 We get a sorted
array 3, 4, 7, 8 , 12 : 8 * 2 - 4 = 12 (there is 12, so the sequence is found)

Answer 3

For the first number, build an array of differences with each of the others, which is to the right.
For the second array of differences with those to the right.
And so for everyone.
Then, in the arrays of these differences, find at least two identical ones.