假设我有3 个Python字典，看起来像这样：

1: {a: ["j"], b: [True], c:["p", "x"]} 
2: {a: ["j"], b: [False], c:["s", "t"]}
3: {a: ["j"], b: [True], c:["x", "z"]}

我想找到所有的“重叠”字典对。

其中dict1和 dict2被认为是“重叠”的当且仅当：

• 它们所有不相同的列表之间，至少包含一个在两者都存在的元素。

在上面的示例中，字典1 与字典3 之所以重叠，是因为它们的 a 和 b 的值相同。而它们的 c 值包含一个共同元素 x。

下面是一些约束条件

• 字典中的每对键值对，其值都保证是一个列表。
• 所有字典具有相同的键。
• 字典的数量可能很大。
• 每个字典可能包含大量的键。

我认为这是一个 O(n^2) 的问题。我找不出一种对这些字典进行排序的方法，使我只需将每个字典与它前后相邻的一个字典比较一次。

因此，我似乎被卡住，只能穷举地将每个字典与其他字典逐一比较，来查看它们是否重叠。

是否有更高效的办法？怎么做？

解决方案

如果你在寻找所有可接受的对，那么输出大小可能达到 Θ(n^2)，这意味着不存在渐进意义上的更快算法。显然地说，例如如果所有字典都完全相同，那么所有字典对都会重叠（因为不存在任何不匹配的列表，所以它们对条件自然而然成立）。

注意，暴力解法的O(n^2) 复杂度假设你可以在O(1) 时间测试两个列表是否相交，但实际情况并非如此，不过通过一些预计算（集合/位图技巧），你可以接近这个上限。