如何在Python3中更快地查找列表的子数组？

Question

这是我的代码：

A = list(map(int, input().rstrip().split()))
sub = [A[i:i+j] for i in range(0,len(A)) for j in range(1,len(A)-i+1)]
print(sub)

我想知道是否有比我更快地找到子数组的方法。列表'A'中的输入数量可以从1到10 ** 5，而输入的值可以从1到10 ** 9。

编辑：

一些输入数据样例：

[1,0,3,0,4]

[1,10,10]

[2,6,13,4,3,2]

注意: 这只是一些小样本，不是真正的大型样本。

- Mahir Islam

---

你能提供一个小的样例输入和期望输出吗？ - user3483203

这有点像超集问题。没有更简单的计算算法。但是，你可以使用 itertools.combination。 - cs95

我建议您稍微修改一下您的答案。让 A = [1, 2, 3, 4]，运行您的代码并生成一些输出，以便您可以将其粘贴在这里，让我们了解您想要做什么。如果我没错的话，这将解决您的问题：[A[i : j] for i, j in itertools.combinations(range(len(A) + 1), 2)]。 - cs95

你需要一次计算所有的值吗？如果你每次只需要使用一个值，那么你可以通过重复使用同一个列表来避免一些数据复制开销。 - Blckknght

一个O(n)的解决方案也会很有帮助。 - Mahir Islam

Answer 1

如果您不需要同时拥有所有结果（例如，您只需要打印每个结果，然后可以忘记它），那么您可以通过重复使用相同的列表而不是在每次迭代中重新切片，将代码的速度从O（N**3）提高到O（N**2）。

def print_subsequences(A):
    for i in range(len(A)):
        result = []
        for j in range(i,len(A)):
            result.append(A[j]
            print(result)

示例输出：

>>> print_subsequences([1,2,3,4])
[1]
[1, 2]
[1, 2, 3]
[1, 2, 3, 4]
[2]
[2, 3]
[2, 3, 4]
[3]
[3, 4]
[4]

你还可以将函数设置为生成器，以产生result而不是打印它们。但这有点危险，因为产生的列表并不都是彼此独立的。如果使用者试图保存示例输出中的[2]列表，他们会发现在下一次迭代后它被更改为包含[2,3]，并且在其后的迭代中进一步更改为[2,3,4]。如果他们仍需要裸的[2]列表，那可能会是一个非常不愉快的惊喜。如果你选择这条路，你需要非常清楚地记录生成器。

- Blckknght