arrays - 使用二进制搜索查找最大子数组

Question

你有两个数组 arr1 和 arr2，你想找到一个既是 arr1 又是 arr2 的子数组的子数组的最大大小

例如:

arr1 = [3,2,1, 4,5]
arr2 = [1,2,3,4,3,2,1]
return is 3 ([3,2,1])

这个问题有一个二进制搜索解决方案，它给你

O(nlogn) 

复杂性。

有谁知道如何解决这个问题？

Answer 1

所以我要提供一个总体思路。如果句子结构不清晰，有人编辑答案

好的，那么我们怎么知道二分查找在这里适用呢，假设我们取mid = (l + (r - l)/2)作为最长公共(public)子数组的长度。 现在，如果我们有一个长度为 L 的公共(public)子数组，则必须有一个长度小于 L 的公共(public)子数组，如果两个数组没有长度为 L 的公共(public)子数组，则它们不能有任何长度大于 L 的公共(public)子数组L. 所以现在实现二分搜索搜索应该很简单，我们检查 mid 这是我们可能的长度，如果存在的话 一个大小为 mid 的公共(public)子数组，如果是，则存在可能存在更大长度的公共(public)子数组的可能性，因此我们将当前满足的长度存储为答案并使 l = mid + 1 ，以检查更多可能的更大长度，如果在某个二进制搜索的迭代我们看到不存在长度为 mid 的公共(public)子数组，没有增加长度的意义所以我们选择更小的长度，即 r = mid - 1。 用c++写代码

  int l = 1 , r = min(array1.size() , array2.size()); // taking min length of array 1 and array2
  int answer = -1;
  while(l <= r)
  {
      int mid = ( l + ( r - l) / 2);
      if(check(array1 , array2 , mid))
      {
          answer = mid;
          l = mid + 1;
     }
     else
       r = mid - 1;
 }
 cout << answer << "\n";

现在问题来了，我们如何检查给定长度 L 和两个数组，如果在给定长度 L 的两个数组中存在一个公共(public)子数组，那么你必须知道实际上试图给出的散列一个数组的唯一数值，这样就可以很容易地比较两个不同的数组，即两个相同的数组将具有相同的哈希值，而不同的数组将具有不同的哈希值。所以存在不同的散列方法，但正如您所猜测的那样，它们可能是两个不同的数组具有相同散列的情况，这称为冲突，那么我们如何减少它我们可以通过使用强散列方法来减少它减少碰撞概率。其中一种方法是滚动散列，有关更一般的想法，请查看互联网上的滚动散列。

现在在二分查找的每一次mid检查中，计算长度为mid的所有子数组的rolling hash，并将其存储在hashtable或set等数据结构中。然后再次计算第二个数组中长度为 mid 的所有子数组的滚动哈希，但是这次在计算时，只检查这个哈希值是否已经计算并存储在你的数据结构中，用于第一个数组的子数组，在哈希表中(平均查找时间是O(1)) 或设置(平均查找时间是对数)，如果是，那么这个中等长度的公共(public)子数组存在并且你返回 true 到二进制搜索，但是在每次检查第二个数组中长度为 mid 的窗口之后，你不如果找不到任何已经存在的散列，则返回 false。 所以假设你把哈希表作为一种数据结构，总的时间复杂度将是

( array1.size() + array2.size() ) * log( min( array1.size() , array2.size() ) )

因为您在二进制搜索中迭代了 log(min(array1.size() , array2.size()) 次，并且在每次迭代中，您通过遍历检查两个数组，计算滚动哈希并检查哈希表，即(array1 .size() + array2.size()).