设计算法比较等长有序列表并统计共同元素数量（非集合实现）

嘿，既然两个列表都是有序且长度相同的，咱们完全可以用双指针这种基础的数组遍历技巧来解决，不用依赖集合的内置方法，刚好能练手数据结构的基础逻辑！

核心思路 #

因为列表是有序的，我们可以用两个指针分别从两个列表的起始位置开始遍历，通过比较当前指针指向的元素来调整指针位置：

• 如果两个元素相等，说明找到一个共同元素，计数加1，同时把两个指针都向后移动一位
• 如果列表a的当前元素更小，就把a的指针向后移（因为a后面的元素更大，才有可能匹配b当前的元素）
• 如果列表b的当前元素更小，就把b的指针向后移
  直到其中一个指针超出列表的长度，遍历就结束了。

代码实现（Python） #

def count_common_elements(a, b):
    # 初始化两个指针，分别指向两个列表的起始位置
    i = j = 0
    count = 0
    # 只要两个指针都没超出列表长度，就继续遍历
    while i < len(a) and j < len(b):
        if a[i] == b[j]:
            count += 1
            i += 1
            j += 1
        elif a[i] < b[j]:
            i += 1
        else:
            j += 1
    return count

# 测试示例
a = [2, 9, 15, 27, 36, 40]
b = [9, 11, 15, 23, 36, 44]
print(count_common_elements(a, b))  # 输出：3

为什么这个方法高效？ #

这个算法的时间复杂度是O(n)，其中n是列表的长度——因为每个指针最多只遍历列表一次，没有嵌套循环，比暴力遍历（O(n²)）高效得多，而且完全基于数组的基础操作，非常适合理解有序列表的遍历逻辑。

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