生成所有连续子数组的算法

Question

使用以下输入，

[1, 2, 3, 4]

我正在尝试获得以下输出

[[1], [1, 2], [1, 2, 3], [1, 2, 3, 4], [2], [2, 3], [2, 3, 4], [3], [3, 4], [4]]

目前我已经做了这样的算法，但是时间复杂度不好。

def find(height):

    num1 = 0

    out = []

    for i in range(len(height)):

        num2 = 1

        for j in range(len(height)):

            temp = []

            for x in range(num1, num2):

                temp.append(height[x])

            num2 += 1

            if temp: out.append(temp)

        num1 += 1

    return out

有什么办法可以加速该算法吗？

Answer 1

连续子序列OP 在评论中指出他们对连续的子序列感兴趣。选择连续子序列所需的只是选择起始索引i和结束索引j。然后我们可以简单地返回切片l[i:j]。def contiguous_subsequences(l):  return [l[i:j] for i in range(0, len(l)) for j in range(i+1, len(l)+1)]print(contiguous_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]]这个函数已经在 more_itertools 包中实现，它被称为substrings：import more_itertoolsprint(list(more_itertools.substrings([0, 1, 2])))# [(0,), (1,), (2,), (0, 1), (1, 2), (0, 1, 2)]不连续的子序列为了完整性。查找可迭代对象的“幂集”是itertool 的秘诀：import itertoolsdef powerset(iterable):    "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"    s = list(iterable)    return itertools.chain.from_iterable(itertools.combinations(s, r) for r in range(len(s)+1))它也在包more_itertools中：import more_itertoolsprint(list(more_itertools.powerset([1,2,3,4])))# [(), (1,), (2,), (3,), (4,), (1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4), (1, 2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4), (1, 2, 3, 4)]

Answer 2

您可以简单地在一行 ( ) 中使用列表理解来完成此操作O(N^2)，这比您现有的方法更快：>>> x = [1,2,3,4]>>> [x[i:j] for i in range(len(x)) for j in range(i+1,len(x)+1)] [[1], [1, 2], [1, 2, 3], [1, 2, 3, 4], [2], [2, 3], [2, 3, 4], [3], [3, 4], [4]]运行时间比较：# your solution>>> %timeit find(x)9.23 µs ± 445 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)#itertools method suggested by 'stef' >>> %timeit list(more_itertools.substrings([1, 2, 3,4]))3.18 µs ± 20.1 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)#List comprehension method>>> %timeit [x[i:j] for i in range(len(x)) for j in range(i+1,len(x)+1)]3.09 µs ± 27.5 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

Answer 3

怎么样：a = [1, 2, 3, 4]l = len(a)ret = []for i in range(l):&nbsp; &nbsp; ll = i + 1&nbsp; &nbsp; while ll <= l:&nbsp; &nbsp; &nbsp; &nbsp; ret.append(a[i:ll])&nbsp; &nbsp; &nbsp; &nbsp; ll +=1print(ret)印刷：[[1], [1, 2], [1, 2, 3], [1, 2, 3, 4], [2], [2, 3], [2, 3, 4], [3], [3, 4], [4]]

Answer 4

这里的时间复杂度是O(N^2)。我不确定这个问题的时间复杂度是否可以进一步降低 ́_(ツ)_/̊。def find(arr):    d = {}    d[0] = []    i = 1    while (i <= len(arr)):        d[i] = [] + d[i - 1]        val = arr[i - 1]        j = i - 1        l = len(d[i - 1])        while (j > 0):            d[i].append(d[i - 1][l - j] + [val])            j = j - 1        d[i].append([val])        i = i + 1    return d[len(arr)]input = [1, 2, 3, 4]print(find(input))输出：[[1], [1, 2], [2], [1, 2, 3], [2, 3], [3], [1, 2, 3, 4], [2, 3, 4], [3, 4], [4]]