数字列表中的算术序列

Question

对于给定的一组数字

3 5 3 6 3 4 10 4 5 2

我希望找到所有**triplets**形成算术级数的东西.

like (3,3,3) (3,4,5) (6,4,2) (3,4,5)

我有一个简单的O(n ^ 3)解决方案.我想知道是否可以在O(n ^ 2)或更短时间内完成.

任何帮助都非常感谢.

Answer 1

O(n^2 * logn) 可通过以下方式实现:

1. 对数组进行排序 - O(nlogn)
2. 迭代所有对(O(n ^ 2)) - 并且对于每对(x,y)进行二进制搜索以查看您是否具有:max{x,y} + abs(x-y)或min{x,y} - abs(x-y)作为元素.
   对于哪些配对应特别小心x==y- 但它可以在相同的时间复杂度内轻松解决.

请注意,此解决方案将为您提供每个三元组的1次出现(无重复).

(编辑:通过使用哈希表(直方图,如果你关心三元组的数量)并查看它而不是排序数组和使用二进制搜索 - 你可以减少O(n^2)平均时间,O(n)增加额外空间的成本).

没有1出现的缺点 - 它不可能做得更好O(n^3),因为可能有O(n^3)这样的三元组,例如在数组中[1,1,1,...,1]- 你有chose(3,n)这样的三元组.