我昨天在算法测试中遇到了这个问题，但我无法弄清楚答案。这让我非常抓狂，因为它值 40 分左右。我认为大多数班级都没有正确解决它，因为我在过去 24 小时内没有提出解决方案。
给定一个长度为 n 的任意二进制字符串，如果存在的话，在字符串中找出三个等距的字符串。编写一个算法，在 O(n * log(n)) 时间内解决这个问题。
所以像这样的字符串有三个“均匀间隔”的字符串：11100000、0100100100
编辑：它是一个随机数，所以它应该能够适用于任何数字。我给出的例子是为了说明“均匀分布”的属性。所以 1001011 是一个有效的数字。1、4和7是均匀分布的。
最后！跟进答案中的线索，我们有它：该问题的 O(n log n) 算法！也很简单，等你明白了。那些猜测 FFT 的人是对的。
问题：给定一个S长度为 n 的二进制字符串，我们想在其中找到三个均匀间隔的 1。例如，S可能是110110010，其中 n = 9。它在位置 2、5 和 8 处均匀分布 1。
S
110110010
S从左到右扫描，并制作一个L位置列表 1。对于S=110110010上面，我们有列表 L = [1, 2, 4, 5, 8]。这一步是 O(n)。现在的问题是找到 长度为 3 in的算术级数L，即找到不同 的 a、b、c inL使得 ba = cb 或等效地 a+c=2b 。对于上面的示例，我们想要找到级数 (2, 5, 8)。
L
S=110110010
为 中的每个 k 制作一个 多项式 p，其中包含 x k_项。对于上面的示例，我们使多项式 _p(x) = (x + x 2 + x 4 + x 5 +x 8 ) 。这一步是 O(n)。 L
p
使用快速傅里叶变换求多项式q= p 2。对于上面的示例，我们得到多项式 q(x) = x 16 + 2x 13 + 2x 12 + 3x 10 + 4x 9 + x 8 + 2x 7 + 4x 6 + 2x 5 + x 4 + 2x 3 + x 2 。 这一步是 O(n log n)。* __ *
q
忽略所有项，除了对应于 x 2k_的一些 _k in L。对于上面的例子，我们得到了 x 16、 3x 10、 x 8、 x 4、 x 2。如果您选择这样做，这一步是 O(n)。
这是关键点：任何x 2b_对于 _b inL的系数 恰好 是对 (a,c) in的数量L，使得 a+c=2b 。[CLRS，前。30.1-7] 这样的一对总是 (b,b) （因此系数至少为 1），但如果存在任何其他对 (a,c) ，则系数至少为 3，来自 (a,c ) 和 (c,a) 。对于上面的例子，我们有 _x 10_的系数正好是 3，因为 AP (2,5,8)。（这些系数 _x 2b_由于上述原因，将始终是奇数。q 中的所有其他系数将始终是偶数。）
因此，算法是查看这些项 x 2b_的系数，看看它们中是否有任何大于 1。如果没有，则没有均匀间隔的 1。如果存在 _x 2b 的 系数大于1的 b ，则我们知道存在一些对 (a,c) --而不是 (b,b) -- 对于其 a+c=2b 。要找到实际的对，我们只需尝试每个 a in （对应的 c 将是 2b-a ）并查看 2b-a in位置是否有 1 。这一步是 O(n)。L L S
就是这样，伙计们。
有人可能会问：我们需要使用 FFT 吗？许多答案，例如beta’s、flybywire’s和rsp ‘s，表明根据直觉检查每对 1 并查看“第三”位置是否有 1 的方法可能在 O(n log n) 中有效如果 1 太多，我们很容易找到三元组，如果 1 太少，检查所有对只需要很少的时间。不幸的是，虽然这种直觉是正确的并且简单的方法 比 O(n 2 ) 更好，但并没有明显更好。正如sdcvvc的回答一样，我们可以采用长度为 n=3 k的字符串的“Cantor-like set”，在其三元表示中只有 0 和 2（没有 1）的位置处有 1。这样的字符串有 2 k = n (log 2)/(log 3) ≥ n 0.63_个，并且没有均匀间隔的 1，因此检查所有对将是其中 1 数量的平方的顺序：那是 _4 k≥ n 1.26，不幸的是，它渐近地远大于 (n log n)。事实上，最坏的情况更糟：Leo Moser 在 1953 年（有效地）构造了这样的字符串，其中包含 n 1-c/鈭…(log n) 1，但没有均匀间隔的 1，这意味着在这样的字符串上，简单的方法是 螛(n 2-2c/鈭�(log n) )——只比 螛(n 2 )好一 点点 ，令人惊讶！ __
关于长度为 n 的字符串中 1 的最大数量，没有 3 个均匀间隔的 1（我们在上面看到，从简单的 Cantor 式构造中至少为 n 0.63，并且至少为 n 1-c/-(log n)_与 Moser 的构造）——这是OEIS A003002。它也可以直接从OEIS A065825计算为 k 使得 A065825(k) ≥ n < A065825(k+1)。我写了一个程序来找到这些，结果发现贪心算法 _没有 给出最长的这样的字符串。例如，对于 n =9，我们可以得到 5 个 1（110100011）但贪心只给出 4（110110000），对于 n =26 we can get 11 1s (11001010001000010110001101) but the greedy gives only 8 (11011000011011000000000000), and for n =74 we can get 22 1s (11000010110001000001011010001000000000000000010001011010000010001101000011) but the greedy gives only 16 (11011000011011000000000000011011000011011000000000000000000000000000000000). 不过，他们确实在很多地方都同意，直到 50 岁（例如，所有 38 到 50 岁）。正如 OEIS 参考资料所说，Jaroslaw Wroblewski 似乎对这个问题很感兴趣，他维护了一个关于这些非平均集的网站。确切的数字只有 194 个。
