如何高效查找Python列表/Numpy数组的最长公共连续子序列（非交集）

先明确核心需求：我们要找的是同时出现在两个序列中的连续元素段，而非简单的元素交集。暴力枚举所有子序列对10万级别的数据完全不现实，下面提供几种高效实现方案：

针对普通Python列表的哈希映射法 #

核心思路是先记录第二个列表中每个元素的所有出现位置，再遍历第一个列表，逐个元素匹配最长连续段：

def find_longest_common_subseq(list1, list2):
    # 构建元素到list2索引列表的映射
    elem_positions = {}
    for idx, val in enumerate(list2):
        elem_positions.setdefault(val, []).append(idx)
    
    max_length = 0
    longest_subseq = []
    
    for i in range(len(list1)):
        current_val = list1[i]
        # 当前元素不在list2里，直接跳过
        if current_val not in elem_positions:
            continue
        # 遍历当前元素在list2的所有位置，尝试匹配连续段
        for j in elem_positions[current_val]:
            current_match_len = 0
            # 向后同步移动指针，匹配连续元素
            while (i + current_match_len < len(list1) 
                   and j + current_match_len < len(list2) 
                   and list1[i + current_match_len] == list2[j + current_match_len]):
                current_match_len += 1
            # 更新最长子序列
            if current_match_len > max_length:
                max_length = current_match_len
                longest_subseq = list1[i:i+current_match_len]
            # 剩余元素长度不足超过当前最长，直接终止循环
            if len(list1) - i <= max_length:
                break
    return longest_subseq

# 测试示例
list1 = [1,2,3,5,4,6,9,8]
list2 = [3,8,2,3,5,4,1,2]
print(find_longest_common_subseq(list1, list2))  # 输出 [2,3,5,4]

这个方法通过提前记录位置避免了重复遍历，还加入了提前终止的优化，比暴力法效率提升明显。

针对Numpy数组的字符串匹配法 #

利用Python标准库的SequenceMatcher（底层优化的动态规划实现），把数组转成带分隔符的字符串，避免元素拼接歧义（比如1和21不会被误判）：

import numpy as np
from difflib import SequenceMatcher

def find_longest_common_subarray(arr1, arr2):
    # 转成带分隔符的字符串，确保元素边界清晰
    sep = '|'
    str1 = sep + sep.join(map(str, arr1)) + sep
    str2 = sep + sep.join(map(str, arr2)) + sep
    
    # 找最长匹配块
    matcher = SequenceMatcher(None, str1, str2)
    best_match = max(matcher.get_matching_blocks(), key=lambda x: x.size)
    
    if best_match.size == 0:
        return np.array([])
    # 把匹配的字符串转回数组
    matched_str = str1[best_match.a : best_match.a + best_match.size]
    return np.array(list(map(int, matched_str.split(sep)[1:-1])))

# 测试示例
arr1 = np.array([1,2,3,5,4,6,9,8])
arr2 = np.array([3,8,2,3,5,4,1,2])
print(find_longest_common_subarray(arr1, arr2))  # 输出 [2 3 5 4]

SequenceMatcher的时间复杂度接近O(n+m)，处理10万级数据完全可行。如果需要找所有公共连续子序列，只需要遍历matcher.get_matching_blocks()的所有非零长度块即可。

注意事项 #

• 如果元素是复杂对象，需要自定义可唯一标识的字符串转换规则，确保匹配准确。
• 若要追求极致性能，还可以用后缀数组算法，但实现复杂度较高，上述两种方案足以覆盖大部分场景。

内容的提问来源于stack exchange，提问作者HTF-struggle