algorithm - 数字列表中的算术序列

Question

对于给定的一组数字

3 5 3 6 3 4 10 4 5 2

我希望找到构成等差级数的所有**三元组**。

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 次(无重复)。

(编辑:通过使用哈希表(histogram 如果您关心三元组的数量)并查看它而不是对数组进行排序和使用二进制搜索 - 您可以减少时间平均为 O(n^2)，额外空间为 O(n)。

---

没有 1 次出现的缺点 - 它不能比 O(n^3) 做得更好，因为可能有 O(n^3) 这样的三元组，对于数组 [1,1,1,...,1] 中的示例 - 您有 choose(3,n) 这样的三元组。