如何基于二分查找寻找两个数组的最长公共子数组？

嘿，这个问题的二分查找解法思路其实挺清晰的，核心就是通过二分枚举可能的最长子数组长度，再用高效的哈希验证来判断可行性，整体时间复杂度能控制在O(n log n)级别。具体拆解下来是这样的：

1. 确定二分的搜索范围 #

最长公共子数组的长度不可能超过两个数组中较短的那个，所以我们的搜索范围是从0到min(len(arr1), len(arr2))。这个范围是天然有序的——如果存在长度为k的公共子数组，那所有小于k的长度肯定也存在；反之如果k不存在，更长的长度更不可能有。完美符合二分查找的适用条件。

2. 关键：高效的验证函数 #

我们需要一个辅助函数is_exist(k)，用来判断是否存在长度为k的子数组同时出现在两个数组中。这里绝对不能暴力枚举所有子数组（暴力的话验证步骤就是O(n²)，整体时间就超了），得用**滚动哈希（Rabin-Karp算法）**来实现O(n+m)的验证：

• 先处理特殊情况：如果k=0，直接返回True（空数组肯定是公共的）；
• 对arr1中所有长度为k的子数组计算哈希值，把这些哈希值存入一个哈希集合；
• 再遍历arr2，计算每个长度为k的子数组的哈希值，检查是否有哈希值在之前的集合里。如果有，说明存在匹配的子数组，返回True；否则返回False。

滚动哈希的优化细节 #

为了快速计算子数组的哈希值，我们可以预处理前缀哈希和基数的幂次数组：

• 选一个大的基数（比如911382629）和一个大模数（比如2^64，或者10^18+3），尽量降低哈希碰撞的概率（也可以用双哈希，两个不同的基数+模数进一步规避碰撞）；
• 计算前缀哈希数组：比如prefix_hash[i]表示arr1[0..i-1]的哈希值，那么子数组arr1[i..i+k-1]的哈希值可以通过公式快速计算：hash = prefix_hash[i+k] - prefix_hash[i] * power[k]（具体公式根据前缀哈希的定义调整）；
• 用同样的方式处理arr2，然后对比哈希集合即可。

3. 二分查找的迭代过程 #

我们用迭代的方式进行二分：

• 初始化ans = 0（记录最长的有效长度），left = 0，right = min(len(arr1), len(arr2))；
• 当left <= right时：
  • 计算中间值mid = (left + right) // 2；
  • 如果is_exist(mid)返回True：说明存在长度为mid的公共子数组，我们可以尝试找更长的，所以更新ans = mid，并把left设为mid + 1；
  • 如果返回False：说明mid太长了，不存在这么长的公共子数组，把right设为mid - 1；
• 循环结束后，ans就是我们要找的最长公共子数组的长度。

用示例验证一下 #

拿题目里的例子：arr1 = [3,2,1,4,5]，arr2 = [1,2,3,4,3,2,1]

• 初始left=0，right=5；
• mid=2：验证发现存在长度2的公共子数组（比如[2,1]），所以ans=2，left=3；
• mid=4：验证长度4的子数组，arr1里的子数组都不在arr2里，所以right=3；
• mid=3：验证长度3的子数组，arr1里的[3,2,1]和arr2末尾的[3,2,1]匹配，所以ans=3，left=4；
• 此时left>right，循环结束，返回3，完全符合预期。

时间复杂度分析 #

• 二分查找的次数是O(log min(n,m))，其中n和m是两个数组的长度；
• 每次验证的时间是O(n+m)（预处理前缀哈希+遍历子数组）；
• 整体时间复杂度就是O((n+m) log min(n,m))，当两个数组长度接近时，就等价于O(n log n)，完全满足题目要求。

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