计算相似数大于K的子阵列

Question

两个阵列X和Y的相似数，每个具有大小N，被定义为索引对（i，j）的数量，使得X [i] = Y [j]，对于1 <= i，j

现在我们给出两个大小为N和M的数组。我们需要从这两个数组中找到相同大小的子数组的数量，这样每个子数组的相同数量大于或等于给定数量K.

例如，我们说N = 3，M = 3，K = 1，数组为[1,3,4]和[1,5,3]，那么答案是6

说明：

({1},{1})
({3},{3})
({1,3},{1,5})
({1,3},{5,3})
({3,4},{5,3})
({1,3,4},{1,5,3})

所以这几年= 6

如何解决给定大小为N，M和给定整数K的数组。元素数不能超过2000.K也小于N * M

方法：从大小为N的数组1中形成所有子数组，那些将是N *（N + 1）/ 2并且对于大小为M的数组2相同。然后尝试在每个子数组对之间找到相似性数。但这是非常不公平的做法。什么可以更好的方法来解决这个问题？我认为动态编程可以用来解决这个问题。有什么建议 ？

对于{1,1,2}和{1,1,3}以及K = 1

{[1(1)],[1(1)]}
{[1(1)],[1(2)]}
{[1(2)],[1(1)]}
{[1(2)],[1(2)]}
{[1(1),1(2)],[1(1)]}
{[1(1),1(2)],[1(2)]}
{[1(1)],[1(1),1(2)]}
{[1(2)],[1(1),1(2)]}
{[1(1),1(2)],[1(1),1(2)]}
{[1(2),2],[1(2),3]}
{[1(1),1(2),2],[1(1),1(2),3]}

Answer 1

由于比赛现在结束了，只是为了完整性，这里是我对那里的编辑答案的理解（我从中学到了很多）。假设我们有一个O(1)时间方法来计算两个连续子阵列的相似性，每个阵列中有一个长度为l。然后，对于每对索引，(i, j)，我们可以二进制搜索满足相似性l的最小k（延伸，比如说左边）。 （一旦我们得到最小的l，我们知道任何更大的l也有足够的相似性，我们可以在O(1)时间添加这些计数。）在这种情况下的总时间将是O(M * N * log(max (M,N))。

好吧，事实证明，有一种方法可以计算O(1)中两个连续子阵列的相似性：矩阵前缀 - 和。在矩阵中，A;如果第一个数组的A(i,j)th元素等于第二个数组的1th元素，则每个条目i为j，否则为0; A矩形A(i-l, j-l)，A(i,j)（左上角到右下角）中O(1)元素的总和正是如此。并且我们可以使用矩阵前缀和计算O(M*N)时间中的和，给定qazxswpoi预处理。