有什么更快的方法可以找到“幸运三元组”的数量？

我正在研究一个代码挑战问题——“寻找幸运三元组”。 “幸运三重”被定义为“在列表中lst，对于三元组的任意组合(lst[i], lst[j], lst[k]) where i < j < k, where lst[i] divides lst[j] and lst[j] divides lst[k].

我的任务是找到给定列表中幸运三元组的数量。蛮力的方法是使用三个循环，但解决问题需要花费太多时间。我写了这个，系统响应“时间超出”。这些问题看起来愚蠢而简单，但数组未排序，因此像二分搜索这样的通用方法不起作用。我被这个问题困扰了一天，希望有人能给我提示。我正在寻求一种更快地解决问题的方法，至少时间复杂度应该低于 O(N^3)。

一个简单的类似动态规划的算法将在二次时间和线性空间中完成此操作。你只需要维护一个计数器c[i]对于列表中的每一项，表示之前整除的整数的数量L[i].

然后，当您浏览列表并测试每个整数时L[k]与所有之前的项目L[j], if L[j]划分L[k]，你只需添加c[j]（可能是 0）到你的全局三元组计数器，因为这也意味着存在确切的c[j] items L[i]这样L[i]划分L[j] and i < j.

int c[] = {0}
int nbTriples = 0
for k=0 to n-1
  for j=0 to k-1
    if (L[k] % L[j] == 0)
      c[k]++
      nbTriples += c[j]
return nbTriples

可能有一些更好的算法，使用奇特的离散数学来更快地完成它，但如果 O(n^2) 可以，这会做得很好。

关于您的评论：

• Why DP?我们有一些东西可以清楚地建模为具有从左到右的顺序（DP橙旗），感觉就像重用先前计算的值可能很有趣，因为暴力算法多次执行完全相同的计算。

• 如何从中找到解决方案？运行一个简单的示例（提示：最好从左到右处理输入）。在步骤i，计算从这个特定点可以计算的内容（忽略 i 右侧的所有内容），并尝试针对不同的情况一遍又一遍地确定您计算的内容i's：这就是您要缓存的内容。在这里，当你在步骤中看到潜在的三元组时k (L[k] % L[j] == 0），你必须考虑会发生什么L[j]: "它的左边也有一些除数吗？其中每一个都会给我们一个新的三元组。让我们看看...但是等等！我们已经计算出步骤j！让我们缓存这个值！“这就是你跳上座位的时候。