昨天我在算法测试中遇到了这个问题，但我找不到答案。这绝对让我发疯，因为它价值40分。我认为大多数班级都无法正确解决该问题，因为在过去的24小时内我没有提出解决方案。
给定任意一个长度为n的二进制字符串，请在该字符串中找到三个均等的字符串（如果存在）。编写一个算法，可以在O（n * log（n））时间内解决此问题。
因此，这样的字符串具有三个“等间距”的字符串：11100000，0100100100
编辑：这是一个随机数，因此它应该可以处理任何数字。我提供的示例旨在说明“均匀分布”的属性。因此1001011是有效数字。其中1、4和7是等距排列的。
最后！跟进sdcvvc答案中的线索，我们得到了：问题的O（nlogn）算法！了解之后，它也很简单。那些认为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的算术级数 中L，即找到不同 的a，b，C 中L，使得 BA = CB ，或者等效 A + C = 2b中 。对于上面的示例，我们要查找进度（2、5、8）。
L
S=110110010
对于中的每个 k ，用项 x k 构成 多项式 。对于上面的示例，我们使多项式 p（x）=（x + x 2 + x 4 + x 5 + x 8 ） 。此步骤为O（n）。p 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_对应的所有项（对于in中的某些 _k ）L。对于上面的示例，我们得到的术语 X 16，3× 10，X 8，X 4，X 2。如果您选择完全这样做，则此步骤为O（n）。
这里的关键点：任何系数 X 2B_为 _b 中L是 精确 的对数 （A，C） 中L，使得 A + C = 2b中 。[CLRS，例如 [30.1-7]一对这样的对总是 （b，b） （因此系数至少为1），但是如果存在其他对 （a，c） ，那么该系数至少为 （a，c）的3。 ） 和 （c，a） 。对于上面的示例，由于AP（2,5,8），我们的 _x 10_系数正好为3。（这些系数 _x 2b_由于上述原因，将始终为奇数。q中的所有其他系数将始终为偶数。）
因此，该算法将查看这些项 x 2b_的系数，并查看它们中的任何一个是否大于1。如果没有，则没有均匀间隔的1s。如果有 _是 一个 b 在L为其中的系数 X 2b的_是大于1，则我们知道有一些对 （A，C） -比其它 （B，B） 对于其中- _A + C = 2b中 。要查找实际的对，我们只是尝试每 一个 在L（对应 ç 是 2B-A ），看看是否有一个1在位置 2B-A 中S。此步骤为O（n）。
就是这样，伙计们。
有人可能会问：我们需要使用FFT吗？很多答案，如测试的，flybywire的，和RSP的，建议的做法是检查每对1S的，并认为如果有一个1在“第三”的位置，在O可能会工作（N log n）的基础上，直觉如果1太多，我们将很容易找到三元组；如果1太少，则检查所有对都花费很少的时间。不幸的是，虽然这种直觉是正确的，简单的方法 是 优于为O（n 2），它是不是好显著。就像sdcvvc的答案一样，我们可以采用长度为 n = 3 k 的字符串的“类似Cantor的集合”，其中三元表示中只有0和2（无1）的位置为1。 这样的字符串中有 _2 k = n （log 2）/（log 3） ≈n0.63_个，并且没有均匀间隔的1s，因此检查所有对将是其中1s的平方的数量级： _4 ķ ≈ñ 1.26_不幸比渐近大得多（N logn）的。实际上，最坏的情况甚至更糟：1953年，LeoMoser构造（有效）了其中具有 _n 1-c /√（log n） 1s但没有均匀间隔1的弦，这意味着在这样的弦上，简单该方法将花费 Θ（n 2-2c /√（log n））-只有一个 很小的 一点优于 Θ（N 2），令人惊讶！
长度为n的字符串中最大1的个数，没有3个均匀间隔的（我们在上面看到的至少是简单的Cantor型构造的 n为 0.63，而至少 n 1-c /√（log n）_为Moser的结构）-这是OEIS A003002。也可以直接从OEIS A065825计算为k，以使A065825（k）≤n <A065825（k + 1）。我写了一个程序来找到这些字符串，结果证明贪心算法 _不能 给出最长的字符串。例如，对于 n = 9，我们可以获得5 1s（110100011），但是对于 n ，贪婪只给出4（110110000） __= 26我们可以得到11 1（11001010001000010110001101），但是贪心只得到8（11011000011011000000000000），对于 n = 74我们可以得到22 1（11000010110001000001001011010001000000000000000010001011010000010001101000011），但是贪婪只得到16（11011000011011000000000000011011000011011000000000000000000000000000）。不过，他们确实在相当多的地方达成共识，直到50个（例如38个到50个）。如OEIS参考文献所述，Jaroslaw Wroblewski似乎对此问题感兴趣，并且他在这些非平均集合上维护了一个网站。确切数字最多只能知道194。
