给您一个整数数组A，每个整数都在[0，1000]范围内，还有一些数字M。例如，您可能会得到以下输入：
A=[5,6,7,8] m=1
问题是尽可能有效地确定数组A中有多少不同的、非空的子数组，其中最多包含m个偶数例如，对于上面的数组，有八个不同的子数组，最多有一个偶数，如下所示：
[(5, 6, 7), (6, 7), (5, 6), (8), (5), (6), (7), (7, 8)]
这是我到目前为止的解决方案，它在时间o（n3）中运行：
def beautiful(A, m):
subs = [tuple(A[i:j]) for i in range(0, len(A)) for j in range(i + 1, len(A) + 1)]
uniqSubs = set(subs)
return len([n for n in uniqSubs if sum(int(i) % 2 == 0 for i in n)<=m ])
这个问题有更好的解决方案吗？理想情况下，是在线性时间内运行还是至少在O（n^2）内运行？
最佳答案
我相信你可以用后缀树在线性时间内做到这一点这当然不是一个轻量级的解决方案-祝你好运编码一个线性时间算法，以建立一个具有可变大小字母表的后缀树-但这表明这是可能的。
这个主意首先为数组构建一个后缀树，将其视为一个字符串，而不是一个数字列表，其中每个字符都是一个数字。由于您知道所有的数字最多为1000，不同字符的数量是一个常量，因此使用快速后缀树构造算法（例如，sa-is），您可以在时间o（n）内构建后缀树。
后缀树是一种很好的结构，因为它们将相同子串的重复副本折叠到重叠的组中，这使得重复数据消除变得更容易。例如，如果模式[1，3，7]在数组中多次出现，那么根目录将包含一条从[1，3，7]开始的路径。
现在的问题是如何从后缀树到不同子数组的数目。现在，让我们来解决一个更简单的问题-如何计算不同子数组的数量，周期，完全忽略奇偶数的限制？幸运的是，这是一个研究得很好的问题，可以在线性时间内解决实际上，后缀树中编码的每个前缀都对应于原始数组的一个不同子数组，因此您只需计算有多少个前缀这可以通过递归地遍历树来完成，对于树中的每个边，加上沿该边有多少个字符。这可以在时间o（n）内完成，因为长度为n的数组/字符串的后缀树有o（n）个节点，并且我们花恒定的时间处理每个节点（只需查看其上方的边）。
所以现在我们只需要对允许使用的偶数进行限制。这有点复杂，但原因很微妙。直觉上，这似乎不是问题毕竟，我们可以对后缀树做一个DFS，然后，当我们走的时候，计算我们所走过的路径上偶数的数目，一旦超过m就停止。
这种方法的问题是，即使后缀树中有o（n）个节点，边缘也隐式地对长度可以高达n的范围进行编码。因此，扫描边的行为本身可能会将运行时放大到Ω（n2）：访问Θ（n）边并对每个边执行Ω（n）功。
不过，我们可以加快一点。后缀树中的每条边通常表示为原始数组中的一对索引[开始，停止]。所以我们假设，作为一个额外的预处理步骤，我们建立一个even s表，使得Evens[n]返回数组中的偶数，直到并包括位置n。然后我们可以通过计算Evens[start]-Evens[stop]来计算任意范围内的偶数这需要时间O（1），这意味着我们可以按照所跟随的边数（而不是所遇到的字符数）的比例，在时间上聚集在一条路径上遇到的偶数。
…只是有一个复杂的问题。如果我们有一个很长的边，在读取该边之前，我们知道我们在偶数极限之下，而在读取该边之后，我们知道我们在极限之上，会发生什么？这意味着我们需要中途停下来，但我们不确定具体在哪里。这可能需要我们在边上做一个线性搜索来找到交叉点，然后我们的运行时就开始了。
但幸运的是，有办法摆脱这个小困境。（下一节包含@Matt Timmermans发现的改进）作为预处理的一部分，除了evens数组之外，还要构建第二个表kth even，其中ktheven[i]返回数组中第kth偶数的位置。这可以使用Evens数组在time O（n）中构建一旦你有了这个，让我们想象一下你有一个坏的边缘，一个会把你推到极限的边缘如果你知道到目前为止你遇到了多少偶数，你可以确定偶数的索引，它会使你超过极限。然后，您可以在索引O（1）中索引到KEVEN表中查找偶数。这意味着我们只需要在后缀树的每一条边上花费O（1）个工作，将运行时向下推到O（n）！
所以，概括地说，这里是这个问题的线性时间解：
使用快速后缀树构造算法（如s a-is或ukkonen算法）为数组构建后缀树。这需要时间o（n），因为字符串中最多有1000个不同的数字，而1000是一个常量。
在时间o（n）内计算表偶数[n]。
在时间o（n）内计算表ktheven[n]。
在树上执行DFS，跟踪到目前为止遇到的偶数当遇到边[开始，停止]时，使用偶数时间O（1）计算该范围内的偶数如果低于限制，继续递归。如果没有，则使用ktheven表来计算在时间o（1）中有多少边是可用的。无论是哪种方式，都可以通过当前边的可用长度来增加不同子数组数的全局计数。这将对后缀树中的每个o（n）边执行o（1）个功，总共执行o（n）个功。
呸这不是一个容易的问题。我想有一些方法可以简化这个结构，我欢迎大家对如何做到这一点提出意见和建议但这表明，在o（n）时间内解决这个问题确实是有可能的，这并不是很明显的！
关于python - 计算最多具有m个偶数元素的不同子数组的数量，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/51690051/