查找数组中连续元素的所有可能子集的最小时间复杂度算法是什么？

Question

假设我有一个 {2, 5, 0} 的数组。我想找到这个数组的连续元素的所有可能子集。结果应该是：

{2}, {5}, {0}, {2, 5}, {5, 0}, {2, 5, 0}

请注意没有 {2, 0}。

我已经找到并想到了很多解决方案。然而，它们中的大多数具有 O(n²) 或 O(2ⁿ 的时间复杂度).有没有时间复杂度更好的算法来解决这个问题，比如O(nlogn)?

Answer 1

不，不可能比 O(n²) 做得更好。原因是预期输出中的元素数量为 O(n²).

设 i 为子数组的起始索引，j 为结束索引，则对于给定的 i，j 有 n-i 个可能值：

i	number of possibilities for j
0	n
1	n - 1
2	n - 2
..	..
n - 1	1
n	0

第二列的总和表示输出中子数组的总数，即1+2+3+...n，即n(n+1)/2，即 O(n²).

以上推理也描述了一种可能的算法：

function slices(arr):
    n := size_of(arr)
    result := []
    for i := 0 to n-1:
        for j := i + 1 to n:
            sub := arr[i:j]  # a slice from arr starting at i and ending at j
            result.append(sub)
    return result

此伪代码假定数组索引从 0 开始，并且结束索引本身不包含在切片中。

此外，它假定切片不会复制所选子范围内的元素（这会增加复杂性），而只是对给定数组本身范围的引用。实际的实现依赖于语言，但始终有效的是结果不是表示为实际的数组集合，而是表示为 (i, j) 元组的集合。

查找数组中连续元素的所有可能子集的最小时间复杂度算法是什么？

What is the least time complexity algorithm to find all possible subsets of consecutive elements in an array?

algorithm

subset

pseudocode