Python列表生成所有连续子序列的低于O(n²)时间复杂度方案求解

核心结论 #

首先要明确：长度为n的列表，符合要求的连续子序列总数量为n*(n+1)/2，这个数量本身就是*O(n²)*量级，因此不存在时间复杂度低于O(n²)的实现——哪怕只是把所有子序列输出或存储一遍，都需要消耗O(n²)的时间。
你之前遇到的双重循环超时问题，大概率是实现方式存在冗余，或者一次性存储所有子序列导致内存占用过高，可以通过惰性生成的方式优化。

最优实现方案 #

1. 生成器惰性输出（推荐） #

不需要一次性把所有子序列加载到内存，用的时候才生成，运行效率和内存占用都远优于一次性生成所有结果的写法：

def get_continuous_subarrays(lst):
    n = len(lst)
    # 注意原代码j的范围到n，会漏掉最长子序列，这里要调整到n+1
    for i in range(n):
        for j in range(i + 1, n + 1):
            yield lst[i:j]

# 调用示例
lst = [1,2,3]
for subarray in get_continuous_subarrays(lst):
    print(subarray)

输出结果完全符合预期：

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

2. 列表推导式一次性生成 #

如果确实需要拿到所有子序列的列表，用列表推导式的执行效率比逐次extend/append更高：

lst = [1,2,3]
res = [lst[i:j] for i in range(len(lst)) for j in range(i+1, len(lst)+1)]
print(res)

输出：

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

常见误区说明 #

你用itertools.combinations的方案不符合要求是因为：combinations生成的是指定长度的所有元素组合，不要求元素在原列表中的索引连续，自然会出现[1,3]这类非连续的结果，这个接口本身就不适合连续子序列的生成场景。
如果你的需求不是输出所有子序列本身，而是做聚合计算（比如求所有连续子序列的和的最大值、所有子序列的元素和总和等），可以针对具体场景做O(n)或O(nlogn)的算法优化，不需要生成所有子序列实体。

内容的提问来源于stack exchange，提问作者imeetsanghvi