Java技术问询：统计数组A元素序列在更长数组B中的出现次数

嘿，这个问题我刚好处理过类似的场景，给你分享几个实用的实现思路，根据你的数组规模和元素类型选就行！

首先先明确需求核心：我们要找的是数组A的完整连续元素序列在更长的数组B中出现的次数——就像你举的例子，A是['A','B']，B里能匹配到3次，完全符合预期。

1. 暴力匹配法（新手友好，直观易懂） #

这是最容易想到的方法，逻辑简单到一眼就能懂：遍历B中所有能放下A的起始位置，逐个比对元素是否完全匹配，匹配上就计数加1。

举个例子，A长度是2，B长度是10，那起始位置可以从0到8（因为8+2刚好到B的末尾，不会越界）。

用Python实现的话是这样：

def count_sequence_occurrences(A, B):
    count = 0
    len_A, len_B = len(A), len(B)
    # 遍历所有合法的起始索引
    for i in range(len_B - len_A + 1):
        match = True
        # 逐个比对A和B的对应元素
        for j in range(len_A):
            if B[i + j] != A[j]:
                match = False
                break
        if match:
            count += 1
    return count

# 测试你的例子
A = ['A', 'B']
B = ['A', 'B', 'C', 'A', 'C', 'A', 'B', 'B', 'A', 'B']
print(count_sequence_occurrences(A, B))  # 输出3，完美符合预期

优缺点 #

• ✅ 优点：逻辑简单，写起来快，调试也容易，适合小规模数组或者快速验证需求；
• ❌ 缺点：时间复杂度是O(n*m)（n是B的长度，m是A的长度），如果数组特别大，效率会很低。

2. KMP算法（高效优化，适合大规模数组） #

如果你的数组规模很大（比如十万级以上的元素），暴力法就不够看了，这时候可以用KMP算法——它的时间复杂度是O(n + m)，能大幅减少不必要的比对。

KMP的核心是先给A数组生成一个前缀函数数组（LPS），这个数组能帮我们跳过已经比对过的元素，不用回溯B的指针，从而提升效率。

直接上Python实现：

def compute_lps_array(pattern):
    m = len(pattern)
    lps = [0] * m
    length = 0  # 记录最长前缀后缀的匹配长度
    i = 1
    while i < m:
        if pattern[i] == pattern[length]:
            length += 1
            lps[i] = length
            i += 1
        else:
            if length != 0:
                length = lps[length - 1]
            else:
                lps[i] = 0
                i += 1
    return lps

def kmp_count_occurrences(A, B):
    count = 0
    len_A, len_B = len(A), len(B)
    lps = compute_lps_array(A)
    i, j = 0, 0  # i遍历B，j遍历A
    while i < len_B:
        if A[j] == B[i]:
            i += 1
            j += 1
        if j == len_A:
            # 找到一次完整匹配，计数加1
            count += 1
            j = lps[j - 1]
        elif i < len_B and A[j] != B[i]:
            # 利用LPS数组跳过不必要的比对
            if j != 0:
                j = lps[j - 1]
            else:
                i += 1
    return count

# 测试例子
A = ['A', 'B']
B = ['A', 'B', 'C', 'A', 'C', 'A', 'B', 'B', 'A', 'B']
print(kmp_count_occurrences(A, B))  # 输出3

优缺点 #

• ✅ 优点：效率极高，适合处理大规模数组；
• ❌ 缺点：逻辑相对复杂一点，需要理解前缀函数的原理，不过一旦写好可以复用。

3. 字符串拼接法（偷懒神器，仅限特定场景） #

如果你的数组元素都是可以转成字符串的（比如单个字符、数字），而且拼接后不会产生歧义（比如不会出现A的元素拼接后和B的其他元素组合混淆的情况），那可以用这个超简洁的方法：把A和B都转成字符串，然后用字符串的count方法直接统计。

比如你的例子里，A转成"AB"，B转成"ABCACABBAB"，直接统计"AB"的次数就是3，完美匹配。

代码实现：

def string_based_count(A, B):
    # 注意：仅当元素拼接后无歧义时使用！比如元素是单个字符/数字
    str_A = ''.join(map(str, A))
    str_B = ''.join(map(str, B))
    return str_B.count(str_A)

# 测试例子
A = ['A', 'B']
B = ['A', 'B', 'C', 'A', 'C', 'A', 'B', 'B', 'A', 'B']
print(string_based_count(A, B))  # 输出3

注意事项 #

这个方法有局限性：如果A的元素是多字符字符串，比如A是["AB", "C"]，B是["A", "BC"]，拼接后都是"ABC"，但实际数组序列并不匹配，这时候就会出错。所以一定要确保元素拼接后不会产生歧义再用！

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