如果您对最大可能数目有一个限制（将其命名为M），则可以在O（M + n）中得到一个解。

布尔数组false，将A元素的所有值标记为true。然后对于B的每个元素b，检查元素编号Kb是否标记为true。

如果您使用哈希映射而不是大数组，则可以改进它。但是我不认为在这种问题上，哈希映射是一种作弊行为。

无论如何，它将为您提供O（n）进行插入，然后为您提供O（n）进行查询，总计为O（n）。

编辑：

一种可能有用的情况。

• 您有大小为10 ^ 6的未排序向量，因此将它们排序并进行匹配在O（n log n）中，其中n = 10 ^ 6。
• 您需要执行10 ^ 6次此操作（不同的向量），复杂度为O（n * n * log n）。
• 最大值为10 ^ 9。

使用我的想法而不是布尔值，而是使用整数（每次运行都会增加），会给您带来以下复杂性：

• “ O（10 ^ 9）”创建数组（同样复杂的空间）
• 每次运行为O（n），因此总计为O（n * n）。

您正在使用更多空间，但是在这种情况下，速度提高了log（n）〜= 20倍！