线性时间内判断序列A中可构造子序列B的元素

核心逻辑 #

要判断序列A中每个元素是否能参与构造子序列B，关键是确认：对于A[i]，是否存在某个位置k（对应B的第k个元素），使得A[i]可以作为B[k]的匹配项，且A[i]的前半部分能覆盖B的前k个元素，后半部分能覆盖B的k+1到末尾的元素。

只要满足这个条件，就说明存在至少一种构造B的方式会用到A[i]。

具体实现步骤 #

1. 生成前缀匹配数组 prefix #

prefix[i] 表示遍历到A的第i个元素时，能匹配到B的最长前缀的长度（从左到右遍历）：

• 初始化指针 j = 0（指向B当前待匹配的位置）
• 逐个遍历A的元素：
  • 如果 j < len(B) 且 A[i] == B[j]，则 j += 1
  • 将 j 赋值给 prefix[i]

这个步骤时间复杂度为O(N)。

2. 生成后缀匹配数组 suffix #

suffix[i] 表示从A的第i个元素开始，能匹配到B的最长后缀的起始位置（从右到左遍历）：

• 初始化指针 j = len(B) - 1（指向B当前待匹配的位置）
• 从后往前逐个遍历A的元素：
  • 如果 j >= 0 且 A[i] == B[j]，则 j -= 1
  • 将 j + 1 赋值给 suffix[i]（表示需要从B的j+1位置开始匹配后缀）

这个步骤时间复杂度同样为O(N)。

3. 构建元素位置映射表 #

为了快速找到A中所有等于B[k]的元素位置，我们创建一个字典 pos_map：

• 键为元素值，值为该元素在A中所有出现位置的有序列表（按遍历顺序存储）

这个步骤时间复杂度为O(N)。

4. 逐个判断A中元素是否可用 #

对于A中的每个元素A[i]，我们需要找到是否存在B中的位置k，满足：

1. B[k] == A[i]
2. 若i > 0，则 prefix[i-1] >= k；若i == 0，则k必须为0（因为前面没有元素，只能匹配B的第一个元素）
3. 若i < len(A)-1，则 suffix[i+1] <= k+1；若i是最后一个元素，则k+1必须等于len(B)（因为后面没有元素，只能匹配B的最后一个元素）

为了高效筛选符合条件的k，我们可以利用pos_map结合二分查找：

• 对于每个k（0 ≤ k < len(B)），取出pos_map[B[k]]中所有A的位置列表
• 在该列表中，通过二分查找快速定位满足prefix[i-1] >= k和suffix[i+1] <= k+1的位置范围
• 将这些位置对应的result数组值设为true

示例验证 #

以题目中的例子为例：
A = [1,3,2,1,2,3,1,3,2]，B = [1,3,1,2]

计算得到的数组 #

• prefix 数组：[1,2,2,3,3,3,3,3,4]
• suffix 数组：[0,0,0,0,1,1,2,3,3]
• pos_map：{1: [0,3,6], 3: [1,5,7], 2: [2,4,8]}

逐个k验证 #

• k=0（B[0]=1）：筛选A中i满足prefix[i-1]>=0且suffix[i+1]<=1，得到i=0、3，标记为true
• k=1（B[1]=3）：筛选A中i满足prefix[i-1]>=1且suffix[i+1]<=2，得到i=1、5，标记为true
• k=2（B[2]=1）：筛选A中i满足prefix[i-1]>=2且suffix[i+1]<=3，得到i=3、6，标记为true
• k=3（B[3]=2）：筛选A中i满足prefix[i-1]>=3且suffix[i+1]<=4，得到i=4、8，标记为true

最终得到的result数组为：[true,true,false,true,true,true,true,false,true]，与题目示例完全一致。

时间复杂度分析 #

• 前缀/后缀数组生成：O(N)
• 位置映射表构建：O(N)
• 元素可用性判断：每个元素最多被处理一次，每次二分查找的时间为O(logS)（S为该元素在A中的出现次数），总时间为O(NlogN)

整体时间复杂度为O(NlogN)，完全可以处理N=10^5的大规模数据场景。

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