如何有效地获取长度为2或更大的数组的所有子数组?

O(n)?也许如果你有无限的内存和实/虚数系统中的每一个可能的子数组存储起来以便高效访问,那么你当然可以有任何你喜欢的复杂算法。

……但实际上,不管你做得有多有效,你都是在沿着o(n^3)的方向看东西。

>>> [lst[i:j + 1] for i in range(len(lst)) for j in range(i + 1, len(lst))]
[[1, 2], [1, 2, 3], [1, 2, 3, 4], [2, 3], [2, 3, 4], [3, 4]]

一行代码隐藏了两个循环和切片操作,所有这些都增加了复杂性。然而,它是 有效率的 作为 快速的 正如底层算法所允许的那样。

你不能得到你的结果 O(N )无论如何。
就像现在一样 2^N - 1 - N 子数组的大小为1,因此总复杂度为 O(2^N) 因为你必须得到所有的子数组。
为了 O(2 ^ n) 解决方案,你可以寻找众所周知的问题 power set of a set .

你可以试试这个 itertools.combinations() 获取长度为2或更大的所有连续子阵的解决方案:

>>> from itertools import combinations
>>> array = [1, 2, 3, 4]
>>> [array[start:end+1] for start, end in combinations(range(len(array)), 2)]
[[1, 2], [1, 2, 3], [1, 2, 3, 4], [2, 3], [2, 3, 4], [3, 4]]