dart - 检查一个列表是否包含 Dart 中另一个列表的任何元素

Question

我有一个数组:

const list1 = [0, 1, 2];

如何检查其他数组是否包含任何目标数组元素？

例如:

[2, 3] //returns true;

[2, 3, 4] //returns true;

[3, 4] //returns false;

Answer 1

使用 list1.indexWhere(list2.contains) 应该适用于小型列表，但对于大型 列表，渐近运行时复杂度为 O(m * n)其中 m 和 n 是列表的大小。

提出检查一个列表是否包含另一个列表的任何元素的问题的另一种方法是检查两个列表的集合交集是否非空。实现它的直接方法是:

var contains = list1.toSet().intersection(list2.toSet()).isNotEmpty;

由于默认的 Set 实现是一个 LinkedHashSet，因此查找的复杂度为 O(1)，并且计算交集对于 之一是线性的设置。但是，将每个 List 转换为 Set 需要线性时间，使得整个操作需要 O(m + n)。

这是渐近有效的，但它计算整个交集只是为了确定它是否为空，这是一种浪费。您可以通过使用 .any 提前停止并注意 .any 不会从作为 Set 的接收对象中获益来做得更好:

var set2 = list2.toSet();
var contains = list1.any(set2.contains);

请注意，如果您可以首先使用 Set 而不是 List，那么转换成本就会消失并使操作成为 O(m)。