如何比 O(N^2) 更快地获取给定数组的所有子数组?

How can I get all subarrays of a given array faster than O(N^2)?

我正在尝试打印给定数组的所有子数组,如下所示。

given array : [5,3,2,4,1]
subarray : [
    [5],
    [5,3],
    [5,3,2],
    [5,3,2,4],
    [5,3,2,4,1],
    [3],
    [3,2],
    [3,2,4],
    [3,2,4,1],
    [2],
    [2,4],
    [2,4,1],
    [4],
    [4,1],
    [1]
]

我可以用嵌套循环打印它。

但我想知道如何用O(N)O(2^N)实现它。

第一个数组有O(n^2)个子数组

打印它们——无论你如何生成它们——总是至少需要 O(n^2);你总是打印至少 O(n^2) 行,每行至少需要 O(1)。

最后,由于任何 O(n^2) 也是 O(2^n),您已经有了一个可以在 O(2^n) 中运行的算法。

不可能在小于 O(N^2) 的时间内访问每个元素,因为您需要访问每个元素才能打印它。您可以考虑展平阵列,然后打印阵列只会是 O(N),因为现在它只是一个阵列。然而,这种扁平化将花费大于 O(N) 的时间。

您最好的选择是使用双重 for-loop 实现

for(List<T> i : itemArray) {
    for(T j : i) {
       System.out.println(j);
    }
}

按照这些思路打印出您的子数组