algorithm - 在给定的一组数字中找出可能的等差数列 3 的个数

标签 algorithm

给定一组整数,问题包括找到长度为 3 的可能算术级数的数量。整数集可能已排序,也可能未排序。

我可以实现一个简单的暴力破解算法,耗时 O(n^3),但时间效率很重要,整数集可以大到 10^5。这意味着暴力破解显然行不通。任何人都可以用 c++ 推荐一些算法/伪代码/代码吗?

例如:有 4 个数字 5,2,7,8 。显然只有一种这样的可能性 - (2,5,8) 其中公差为 3,所以我们的答案是 1。

编辑:我忘了提及一个重要属性 - 给定的每个集合数都在 1 到 30000 之间(含)。

最佳答案

您可以按如下方式在 O(N^2) 中执行此操作:创建一个整数的哈希集,以便您可以检查 O(1) 中是否存在某个元素。 .之后,对所有集合元素对进行两个嵌套循环 {X, Y} .这是在 O(N^2) 中完成的.

对于每对 {X, Y} ,假设 X < Y , 并计算两个数字:

Z1 = X - (Y-X)
Z2 = Y + (Y-X)

三元组 {X, Y, Zi}如果 Zi != X && Zi != Y && set.contains(Zi) 形成等差数列

检查两个三元组 {X, Y, Z1}{X, Y, Z2} .您可以在 O(1) 中完成使用哈希集,算法的总运行时间为 O(N^2) .

关于algorithm - 在给定的一组数字中找出可能的等差数列 3 的个数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/13324832/

相关文章:

c++ - 需要算法找到第n个回文数

algorithm - 了解解决此问题的更快方法?

c# - 最快的二维数据空间索引,一旦构建就无需更新

c++ - O(klogn) 时间算法从 Fenwick-Tree 中找到第 k 个最小元素

arrays - 给定一个数组,找出每个元素的下一个较小的元素

algorithm - 在图中,找到具有特定属性的最长路径?

c++ - Strassen 算法中的递归

algorithm - 终止函数定义(算法)

algorithm - Diffie-Hellman 协议(protocol)可以用作数字签名的基础吗?

python - 如何获取 round() 函数小数点后的确切位数