检查 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实现是 a LinkedHashSet，因此查找时间复杂度为 O(1)，并且计算交集将相对于 s 之一呈线性Set。然而，将每个转换List为 aSet需要线性时间，使得整个操作需要 O(m + n)。

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

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

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