Bonjour,
Mon but est d'améliorer la complexité de ma solution au problème suivant :
On a un tableau d'entiers t = [t1 < t2 ... < tn]. Le but est de compter le nombre de triplets ti , tk , tj tels que tk - ti = tj - tk.
Ma solution s'exécute en O(n²) (en Python):

s = 0
for k in range(1, n-2):
i,j = k-1, k+1
temp = 2 * t[k]
while i >= 0 and j < n:
if t[i] + t[j] == temp:
s+=1
i-=1
j+=1
elif t[i] + t[j] < temp:
j+=1
else:
i-=1

Par exemple, [1,3,4,5] va donner s = 2.

Y a-t-il une solution plus efficace ?
Merci