Python如何高效统计子列表在另一列表中的连续出现次数

首先明确需求场景：
现有测试列表：

A = [1, 2, 1, 2, 1, 2, 3, 4, 5]

需要统计连续子列表[1,2]的非重叠出现次数，预期返回结果为3，对应匹配位置为列表前6位元素依次组成的3组[1,2]。

原有实现的问题 #

你当前写的代码首先存在缩进语法错误，逻辑层面也有明显的性能缺陷：

• 循环中反复调用tA.pop(0)，Python列表的头插/头删操作时间复杂度为O(n)，每次执行都要移动列表内所有后续元素，数据量稍大时性能会急剧下降
• i in tA是线性扫描查找，会产生大量无意义的遍历，还存在误判非连续匹配的风险
• 整体时间复杂度接近O(n²)，列表长度越长执行效率越低

更高效率的实现方案 #

推荐用单次线性扫描+滑动窗口的写法，时间复杂度O(n)，不需要修改原列表，也没有额外的空间开销，性能比原有实现高几个数量级：

def count_non_overlap_sublist(origin, pattern):
    count = 0
    pattern_len = len(pattern)
    origin_len = len(origin)
    # 边界判断：模式为空或者原列表比模式短直接返回0
    if pattern_len == 0 or origin_len < pattern_len:
        return 0
    
    i = 0
    while i <= origin_len - pattern_len:
        is_match = True
        # 比对当前位置开始的子段和模式是否一致
        for offset in range(pattern_len):
            if origin[i + offset] != pattern[offset]:
                is_match = False
                break
        if is_match:
            count += 1
            i += pattern_len  # 匹配成功跳过整个模式长度，实现非重叠计数
        else:
            i += 1
    return count

# 测试用例
A = [1, 2, 1, 2, 1, 2, 3, 4, 5]
print(count_non_overlap_sublist(A, [1, 2]))  # 输出3，符合预期

如果后续需要统计允许重叠的子序列次数（比如统计[1,1,1]中[1,1]出现2次的场景），只需要把匹配成功后的i += pattern_len改成i += 1即可。

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