如何在O(n²)复杂度下解决数组B删单元素后查A中对应排列问题

核心思路 #

我们需要找到数组A中所有长度为M-1的子数组，只要该子数组是数组B删除任意一个元素后的排列，就记录其起始下标，最终去重后输出结果。

实现步骤 #

• 预处理B：先统计B的元素频率，生成所有删除单个元素后的频率表，去重后存入集合，避免重复校验相同的排列规则
• 遍历A的所有符合长度要求的子数组：子数组固定长度为M-1，统计每个子数组的元素频率，和预处理得到的目标频率集合比对，匹配则记录起始下标
• 结果处理：对记录的下标去重排序后输出

复杂度说明 #

预处理B的时间复杂度为O(M²)，遍历A所有子数组的时间复杂度为O(NM)，整体时间复杂度为O(NM + M²)，属于O(n²)级别，符合题目要求。

代码实现 #

from collections import Counter

def find_valid_indexes(A, B):
    n, m = len(A), len(B)
    target_len = m - 1
    # 边界情况处理：B删完为空，所有下标都符合
    if target_len == 0:
        return list(range(n))
    if n < target_len:
        return []
    
    # 预处理生成所有删除单个元素后的目标频率集合
    original_b_cnt = Counter(B)
    target_freq_set = set()
    # 仅遍历B的唯一元素，避免生成重复的频率表
    for num in original_b_cnt:
        temp_cnt = original_b_cnt.copy()
        temp_cnt[num] -= 1
        if temp_cnt[num] == 0:
            del temp_cnt[num]
        # 转成排序后的元组使其可哈希，存入集合
        target_freq_set.add(tuple(sorted(temp_cnt.items())))
    
    res = set()
    # 遍历所有长度为target_len的子数组
    for i in range(n - target_len + 1):
        window = A[i:i+target_len]
        window_cnt = Counter(window)
        window_tuple = tuple(sorted(window_cnt.items()))
        if window_tuple in target_freq_set:
            res.add(i)
    
    return sorted(list(res))

# 测试题目示例
if __name__ == "__main__":
    A = [1,2,2,1,1]
    B = [1,2,1]
    print(find_valid_indexes(A, B)) # 输出 [0, 2, 3]

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