你得到了n数字，你必须找到对的数量，使得它们之间至少有一个数字是共同的。
例如。对于5 个号码：
2837 2818 654 35 931
答案：6
这里的对是(2837,2818), (2837,35), (2837,931), (2818,931), (654,35), (35,931)
我的尝试：我采用了一个结构，该结构以十进制存储数字，以数组中的数字形式存储数字以及该数字中的位数。
现在对于每个数字，我在包含索引0-9的数组中对该数字进行哈希处理，并检查所有以下数字是否已经存在它们的任何数字。
我的尝试是O(n^2)，这很慢。是否有另一种算法可以更快地工作？
在这里了解什么是变量和什么是常数是至关重要的。
位数是一个常数 (10)。所有数字集的数量（1024）也是如此。此类集合的所有对的数量也是如此（2 20或大约一百万）。让我们利用这一点。
让我们尝试将输入预处理为大小恒定（与输入大小无关）的数据结构中的“等效”表示。然后，我们对这个恒定大小的结构所做的任何事情都被定义为恒定时间操作，因此总运行时间仅由预处理阶段渐近确定。
数据结构
创建一个1024个整数的数组，每个桶（索引）对应一组数字；我们希望在每个桶中存储恰好具有该组数字的输入数字的数量。
例如，3606 有数字 0、3 和 6，因此它将被计入存储桶 2 0 + 2 3 + 2 6 = 73。
算法
预处理是显而易见的。取下一个数字（例如'3'），将其转换为它的值（例如3），现在计算相应的位（例如1 << 3）并将其 OR 为（暂定）桶索引变量；不同的数字占据不同的位，因此每个数字组合都有一个唯一的桶，但我们摆脱了任何重复的数字。像这样循环，直到遇到数字分隔符；那时，桶索引是最终的，我们可以增加桶，重置桶索引并跳到下一个数字。
而已。剩下的就是数我们的羊了。哎呀。成对的羊。
将每个存储桶与其他存储桶（但不是自身）进行比较。每当两个索引共享一个数字时（这可以使用&运算符确定），将这两个存储桶的内容相乘，并将乘积添加到全局维护的总和中。
将每个桶也与其自身进行比较，并仅x * (x - 1) / 2将其与全局维护的总和相加，其中x是桶的内容。
这个总和就是你的结果。
表现
最坏的情况：输入大小 O(n)在哪里。n
常数因素也是有利的。每个数字或分隔符我们需要一些指令（和 RAM 访问）；恒定阶段检查一百万个桶对，在每对桶上花费一些类似的指令（不需要访问 RAM，数据结构非常紧凑）。这是闪电般的速度。
理论家会说这是作弊。我们假设输入长度没有上限（或者我们根本不能谈论渐近复杂度），但我们还假设我们可以将总输入长度放入一个整数变量中。那好吧。
更实际的程序员会注意到该算法的字母大小呈指数级。我们很幸运；如果我们的单词不是由数字组成，而是由除分隔符之外的任意字符组成，那么我们的单词仍将是渐近线性时间算法，但与可以轻松处理到兆字节的幼稚算法相比，它对于任何输入都会非常慢一次输入。
创建一个集合数组，每个数字一个。
迭代您的数字并将每个数字放入每个集合中的数字中。
迭代所有 10 个集合，并将集合中的每个元素与同一集合中的所有其他元素组合。（或所有其他大于自身的元素，如果您不想在结果中出现 (a,b) 和 (b,a) 。
我认为这仍然是 O(n^2) 但可以使用分叉连接方法很好地使其瘫痪。
更新
刚刚意识到你只想要结果的数量。所以这将是所有集合的 size * size-1 的总和。由于插入一个集合并获得它的大小应该是线性的（我认为）这实际上可能是 O(n)
另一个更新
如果您的号码不同，并且您只对成对的数量感兴趣，那么您甚至不需要套数，而只需要一个计数器。
不起作用 来自评论：
Consider 1st pair in above questions test case (2837,2818), this will put first number in set containing digit 2 and 8 and same for 2818 now they are to be counted as one but counting in 2 and 8 will count it twice. I hope you understand what I am trying to say...
所以这种方法行不通……我想这可能对其他人有警告价值。
首先，我注意到常用数字的位置无关紧要。
在这种情况下，我用哈希表勾勒出一个小算法：形成 10 个 bin，每个数字一个。然后，对于每个数字，将（唯一地）该数字的 ID 放入每个 bin 中，对应于它所具有的每个数字。这个操作是O(n*k)，k是数字的位数。最后，要形成所有对，在每个 bin 中取成对的数字。要删除可能的双倍数，请将每对 (a,b) 与 a
我认为最坏的情况实际上是 O(n^2); 事实上，我确实认为这一步必须具有 O(n^2) 的复杂性，因为您想要获取所有对（最大 n*(n+1)/2）。所以最终的复杂度确实是二次的。