理解问题：序列查找与计数
在python编程中，我们经常需要处理列表（或数组）数据。一个常见的需求是检查一个较短的序列（子序列）是否包含在一个较长的列表（主列表）中。然而，仅仅判断子序列是否存在往往不足够，我们可能还需要知道它在主列表中总共出现了多少次。
例如，如果我们有一个主列表 ['A','V','V','V','V','V','E','A','V','V'] 和一个目标子序列 ['A','V','V']，我们希望得到的结果是 2，因为 ['A','V','V'] 在主列表中连续出现了两次。
直接使用如 any(target_sequence == main_list[i:i + n] for i in range(len(main_list) - n + 1)) 这样的方法，虽然可以判断是否存在，但它会在找到第一个匹配项时立即停止并返回 True，无法统计所有出现次数。因此，我们需要一种更精确的计数策略。
核心解决方案：滑动窗口与切片比较
解决这个问题的核心思想是采用“滑动窗口”的方法。我们定义一个与目标子序列长度相同的“窗口”，让这个窗口在主列表上从头到尾滑动。在每一步滑动中，我们截取窗口当前覆盖的子列表，并将其与目标子序列进行比较。如果两者完全匹配，我们就增加一个计数器。
具体步骤如下：
立即学习“Python免费学习笔记（深入）”；
- 确定目标长度： 获取目标子序列的长度 n。
- 初始化计数器： 设置一个变量 x，用于存储匹配次数，初始值为 0。
- 遍历主列表： 使用一个循环，从主列表的第一个元素开始，到 len(主列表) - n + 1 结束。这个范围确保了每次切片都能得到一个完整长度为 n 的子列表，且不会超出主列表的边界。
- 切片与比较： 在循环的每一步 i，从主列表中切取一个子列表 main_list[i : i + n]。然后，将这个切片与目标子序列进行比较。
- 累加计数： 如果切片与目标子序列相等，则将计数器 x 1。
实战代码示例
以下是根据上述逻辑实现的Python代码示例：
# 定义主列表和目标子序列
main_list = ['A','V','V','V','V','V','E','A','V','V']
target_sequence = ['A','V','V']
# 获取目标子序列的长度
n = len(target_sequence)
# 初始化计数器
count = 0
# 遍历主列表，使用滑动窗口进行比较
for i in range(len(main_list) - n + 1):
# 切取当前窗口内的子列表
current_slice = main_list[i : i + n]
# 比较切片与目标子序列
if current_slice == target_sequence:
count += 1 # 如果匹配，计数器加1
# 输出结果
print(f"子序列 {target_sequence} 在主列表 {main_list} 中出现了 {count} 次。")
输出：
子序列 ['A', 'V', 'V'] 在主列表 ['A', 'V', 'V', 'V', 'V', 'V', 'E', 'A', 'V', 'V'] 中出现了 2 次。
代码解析与执行流程
让我们逐步分析上述代码在示例数据上的执行过程：
- main_list = ['A','V','V','V','V','V','E','A','V','V']
- target_sequence = ['A','V','V']
- n = 3 (因为 len(['A','V','V']) 是 3)
- count = 0
循环 for i in range(len(main_list) - n + 1)，即 for i in range(10 - 3 + 1)，也就是 for i in range(8)，i 将从 0 遍历到 7。
-
i = 0:
- current_slice = main_list[0:3] 得到 ['A','V','V']。
- ['A','V','V'] == ['A','V','V'] 为 True。
- count 变为 1。
-
i = 1:
- current_slice = main_list[1:4] 得到 ['V','V','V']。
- ['V','V','V'] == ['A','V','V'] 为 False。
- count 保持 1。
-
i = 2:
- current_slice = main_list[2:5] 得到 ['V','V','V']。
- ['V','V','V'] == ['A','V','V'] 为 False。
- count 保持 1。
-
i = 3:
- current_slice = main_list[3:6] 得到 ['V','V','E']。
- ['V','V','E'] == ['A','V','V'] 为 False。
- count 保持 1。
-
i = 4:
- current_slice = main_list[4:7] 得到 ['V','E','A']。
- ['V','E','A'] == ['A','V','V'] 为 False。
- count 保持 1。
-
i = 5:
- current_slice = main_list[5:8] 得到 ['E','A','V']。
- ['E','A','V'] == ['A','V','V'] 为 False。
- count 保持 1。
-
i = 6:
- current_slice = main_list[6:9] 得到 ['A','V','V']。
- ['A','V','V'] == ['A','V','V'] 为 True。
- count 变为 2。
-
i = 7:
- current_slice = main_list[7:10] 得到 ['V','V',]。
- ['V','V',] == ['A','V','V'] 为 False。
- count 保持 2。
循环结束，最终 count 的值为 2，这正是我们期望的结果。
注意事项与性能考量
- 时间复杂度： 这种方法的平均时间复杂度是 O(N * M)，其中 N 是主列表的长度，M 是目标子序列的长度。这是因为外层循环执行了 N-M+1 次，而每次循环内部的列表切片和比较操作在最坏情况下需要 M 次元素比较。对于大多数常见的列表长度，这种性能是完全可以接受的。
- 空间复杂度： 每次切片会创建一个新的子列表，其空间复杂度为 O(M)。
- 空序列处理： 如果 target_sequence 是一个空列表 []，那么 n 将为 0。此时 range(len(main_list) - 0 + 1) 会导致循环执行 len(main_list) + 1 次。main_list[i:i+0] 始终是 []，所以它会匹配所有可能的位置。如果需要特殊处理空序列，应在函数开头添加一个条件判断。
- 可读性： 这种方法代码直观、易于理解，符合Python的简洁风格。
总结
通过采用滑动窗口和列表切片比较的方法，我们可以有效地在Python列表中查找并统计特定子序列的出现次数。这种方法简单、直接，并且对于大多数应用场景而言，提供了足够的性能。理解其背后的原理和执行流程，有助于我们更好地解决类似的序列处理问题。
