如何高效将Python列表拆分为公差为2的单调子列表？

嘿，这个需求其实用一次线性遍历就能完美解决，这也是时间复杂度最优的方案（O(n)），毕竟我们没法绕过每个元素都处理一遍的过程。

核心思路 #

我们只需要维护当前正在构建的公差为2的子序列，遍历原列表时：

• 从第一个元素开始，初始化第一个子序列
• 后续每个元素和当前子序列的最后一个元素对比，如果差值正好是2，就把它加入当前子序列
• 如果差值不是2，就新建一个子序列，把当前元素放进去，然后继续遍历

Python 实现代码 #

l = [2,4,6,12,14,16,21,27,29,31]
if not l:
    new_l = []
else:
    new_l = [[l[0]]]
    for num in l[1:]:
        # 检查当前元素和当前子序列最后一个元素的公差
        if num - new_l[-1][-1] == 2:
            new_l[-1].append(num)
        else:
            new_l.append([num])

print(new_l)
# 输出结果：[[2,4,6], [12,14,16],[21], [27,29,31]]

为什么这是最高效的？ #

• 时间效率：每个元素只被访问一次，没有嵌套循环或者额外的计算，时间复杂度严格为O(n)，这是这类问题的理论最优解
• 空间效率：除了存储结果所需的O(n)空间（这是无法避免的，因为最终要输出所有元素），只用到了几个简单变量，额外空间可以忽略不计
• 可读性：逻辑直白易懂，不需要依赖任何第三方库，原生Python就能实现，维护起来也方便

如果你的原列表是无序的，那可能需要先排序再用这个方法，但从题目给出的例子来看，原列表是递增的，所以直接用上面的代码就完全没问题。

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