数组求和的快速算法

Question

我正在寻找一个快速的算法：

我有一个大小为n的int数组，目标是在数组中找到所有模式，
x1，x2，x3是数组中不同的元素，这样x1-x2=x3

例如，我知道有一个大小为3的int数组是[1，2，3]，那么只有一种可能性：12=3（考虑12=21）

我正在考虑实现对和Hashmap来使算法快速。（我现在得到的最快的仍然是O（n^2））

请分享你对这个问题的看法，谢谢

Answer 1

你基本上需要找到所有不同的值对和，所以我认为你不会比O做得更好（n²）。但您可以通过对列表进行排序并减少重复值来进行优化，然后只将一个值与任何相等或更大的值配对，当总和超过列表中的最大值时停止。

Answer 2

它必须至少是O（n^2），因为有n（n-1）/2个不同的总和可以检查其他成员。你必须计算所有这些元素，因为任何一对求和的元素都可能是任何其他成员（从一个例子开始，排列所有元素，让自己相信所有元素都必须被检查）。或者看看斐波那契的具体内容。

所以计算并在哈希表中查找成员会得到摊销的O（n^2）。或者如果你需要最好的最坏情况，使用有序树。

Answer 3

编辑：下面的答案适用于这个问题的一个版本，在这个版本中，你只需要一个这样加起来的三元组。当你想要所有这些元素时，因为可能至少有O（n^2）个可能的输出（正如ex0du5所指出的），甚至在重复元素的病理情况下，也有O（n^3），所以你无法击败基于散列（从一个值映射到具有该值的索引列表）的简单O（n^2）算法。

这基本上就是3SUM问题。在没有潜在无限大元素的情况下，最著名的算法大约是O（n^2），但我们只证明，对于大多数计算模型，它不可能比O（n lg n）更快。

如果整数元素在[u，v]范围内，则可以在O（n（v-u）lg（v-u））中使用FFT执行稍微不同的版本。我将描述一个过程，将这个问题转化为那个问题，在那里解决它，然后根据这个转化找出问题的答案。

我知道如何用FFT解决的问题是在数组中找到长度为3的算术序列：即序列a，b，c与c-b=b-a< /code>，或等价地a c=2b。

不幸的是，转变的最后一步并不像我希望的那么快，但是当我们到达那里时，我会谈论这个。

让我们调用原始数组X，它包含整数X_1。。。，x_n。我们想找到索引i，j，k，这样x_i x_j=x_k。

>

在O（n）时间中找到X的最小u和最大v。让u'bemin（u，u*2）和v'bemax（v，v*2）。

构造一个长度v'-u'1的二进制数组（bitString）Z；如果X或其双[x_1*2，...，x_n*2]包含u'i，则Z[i]将为真。这是要初始化的O（n）；只需遍历X的每个元素，并设置Z的两个相应元素。

在构建这个数组时，我们可以将找到的任何重复项的索引保存到一个辅助列表Y。一旦Z完成，我们只需在Y中为每个x_i检查2*x_i。如果有人在场，我们就完了；否则，重复项就无关紧要了，我们可以忘记Y。（唯一稍微复杂一点的情况是，如果重复0，那么我们需要它的三个不同副本来获得解决方案。）

现在，您的问题的解决方案，即x_i x_j=x_k，将在Z中显示为三个等距的一，因为一些简单的代数运算给我们提供了2*x_j-x_k=x_k-2*x_i。注意，在endpoint上的元素是我们特殊的加倍条目（从<代码> 2x< /代码>），中间的条目是一个常规条目（从<代码> x< /html" target="_blank">代码>）。

考虑将Z作为多项式p的表示，其中度i项的系数是Z[i]。如果X是[1,2,3,5]，那么Z是11110001（因为我们有1, 2, 3, 4, 5, 6和10）；p是1 x x²x³x⁴x⁵x⁹。

现在，请记住高中代数中，两个多项式乘积中x^c的系数是所有a，b的和，其中a b=c是x^a的第一个多项式的系数乘以x^b的第二个多项式的系数。因此，如果我们考虑q= p ＞2＜/SUP>，x ^2J系数（对于一个j＜代码＞Z[j]＝1＜/代码>）将是关于<代码> Z[i] *Z[2×J-i] < /代码>的所有i的总和。但是由于 Z是二进制的，这正是 Z中三元组i，j，k的数量，它们是均匀分布的。注意，（j，j，j）总是这样的三元组，所以我们只关心有值的三元组

然后，我们可以使用快速傅立叶变换在O（|Z | log | Z |）时间中找到p2，其中|Z |是v'-u'1。我们得到另一组系数；称之为W。

循环遍历X中的每个x_k。（回想一下，我们想要的均匀间隔的函数都以X元素为中心，而不是2*X。）如果这个元素的两倍对应的W，即W[2*（x_k-u'）]为1，我们知道它不是任何非平凡级数的中心，我们可以跳过它。（如前所述，它应该只是一个正整数。）

否则，它可能是我们想要的级数的中心（所以我们需要找到i和j）。但是，不幸的是，它也可能是没有我们想要的形式的级数的中心。所以我们需要检查。循环查看X的其他元素x_i，并检查是否有2*x_i，x_k，2*x_j（通过检查Z[2*（x_k-x_j）-u']）。如果是这样，我们就有了答案；如果我们通过所有的X而没有命中，那么FFT只找到了虚假的答案，我们必须检查W的另一个元素。

因此，最后一步是O（n*1（与W的x_k数[2*（x_k-u'）]

我认为可以用一个有点不同的多项式来做这件事，但是我还没有让它真正起作用。我会再考虑一下......

部分基于这个答案。