如何高效比较百万级点分隔数字字符串并找出2个及以上共同数字

嘿，我之前在处理大规模数据批量校验的时候遇到过几乎一模一样的问题，原来用array_diff的思路在数据量到百万级之后确实会明显拖慢速度，主要原因是array_diff需要遍历两个数组做全量比较，而且还要后续计算交集数量，累积下来开销非常大。

问题根源分析 #

原代码的逻辑是把两个字符串转成数组，通过差集反推交集数量，但这个方法的时间复杂度是O(n+m)（n和m是两个数组的长度），而且必须处理完所有元素才能得到结果。在百万次循环的场景下，每一次的O(n+m)都会被放大，导致整体性能瓶颈。

优化方案：哈希表+提前终止 #

核心思路是用哈希表（PHP里的关联数组）实现O(1)时间的快速查找，并且一旦找到2个匹配项就立刻终止判断，不用处理完所有元素，这在大多数场景下能大幅减少计算量。

优化后的代码实现

function hasAtLeastTwoCommon(string $s1, string $s2): bool {
    // 将第一个字符串的元素存入哈希表，键为数字串，值标记为存在
    $s1Hash = [];
    foreach (explode(".", $s1) as $num) {
        $s1Hash[$num] = true;
    }

    $matchCount = 0;
    // 遍历第二个字符串的元素，逐个检查是否在哈希表中
    foreach (explode(".", $s2) as $num) {
        if (isset($s1Hash[$num])) {
            $matchCount++;
            // 找到2个匹配项直接返回，无需继续遍历
            if ($matchCount >= 2) {
                return true;
            }
        }
    }

    return false;
}

// 测试示例
$s1 = "32.56.86.90.23";
$s2 = "11.25.32.90.10";
echo hasAtLeastTwoCommon($s1, $s2) ? "YES" : "NO"; // 输出 YES

为什么这个方案更快？ #

1. O(1)快速查找：哈希表的isset操作是常数时间复杂度，比数组遍历比较快得多，尤其是在元素数量较多时。
2. 提前终止逻辑：一旦找到2个共同元素就立刻停止后续遍历，避免了不必要的计算——比如你的示例中，遍历到第二个匹配项（90）就直接返回，不用处理剩下的元素。
3. 更低的内存开销：不需要生成差集数组，只需要存储一个哈希表，内存占用比原方案更小。

进阶优化（针对批量场景） #

如果是批量处理百万对独立的$s1和$s2，上面的代码已经是最优的。但如果是多个$s2对应同一个$s1，可以预先把$s1的哈希表缓存起来，避免重复生成哈希表的开销，进一步提升性能。

另外提一句：原代码里有个小bug——if($result>=2)应该写成if($rt1>=2)，因为$result是差集数组，$rt1才是交集的数量，不过这个不影响性能问题的核心。

内容的提问来源于stack exchange，提问作者gr68